Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38397 hi_hi 【S】T4 C++ 通过 100 70 MS 6500 KB 876 2025-10-03 19:04:51

Tests(10/10):


#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]); }


测评信息: