提交时间:2025-10-03 15:53:27
运行 ID: 38369
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct dn{ ll a,b; }a[200005]; bool cmp(dn x,dn y){ return x.a<y.a; } ll n,dp[200005],nxt[200005],c[200005]; const int mod = 998244353; int main(){ freopen("2.in","r",stdin); freopen("2.out","w",stdout); cin>>n; for(int i = 1;i<=n;i++){ cin>>a[i].a>>a[i].b; c[i]=a[i].a; } sort(a+1,a+n+1,cmp); sort(c+1,c+n+1); dp[n+1]=1; nxt[n+1]=n+1; for(int i = n;i>=1;i--){ nxt[i]=i; int l = 1,r = n+1; while(l+1<r){ int mid = (l+r)>>1; if(c[mid]>=a[i].a+a[i].b){ r=mid; } else { l=mid; } } //printf("%d %d\n",i,l); for(int j = i+1;j<=l;j++){ nxt[i]=max(nxt[i],nxt[j]); } } for(int i = 1;i<=n;i++){ //printf("%d %d %d %d\n",i,a[i].a,a[i].b,nxt[i]); } for(int i = n;i>=1;i--){ dp[i]=dp[i+1]+dp[nxt[i]+1 ]; dp[i]%=mod; } printf("%d\n",dp[1]); }