| Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
|---|---|---|---|---|---|---|---|---|---|
| 38397 | hi_hi | 【S】T4 | C++ | 通过 | 100 | 70 MS | 6500 KB | 876 | 2025-10-03 19:04:51 |
#include<bits/stdc++.h> using namespace std; long long n,nxt[200005],dp[200005],md=998244353; struct sss{ long long a,b; }gp[200005]; bool cmp(sss x,sss y){ return x.a<y.a; } int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld%lld",&gp[i].a,&gp[i].b); } sort(gp+1,gp+n+1,cmp); nxt[n]=n+1; for(int i=n;i>=1;i--){ long long l=i,r=n,ans=n+1; while(l<=r){ long long mid=(l+r)/2; if(gp[i].a+gp[i].b>gp[mid].a){ ans=mid; l=mid+1; } else r=mid-1; } nxt[i]=ans+1; for(int j=i+1;j<=ans;j++){ nxt[i]=max(nxt[i],nxt[j]); } } dp[n+1]=1; for(int i=n;i>=1;i--){ dp[i]=dp[i+1]+dp[nxt[i]]; dp[i]%=md; } printf("%lld",dp[1]); }