| Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
|---|---|---|---|---|---|---|---|---|---|
| 38367 | 黄子睿 | 【S】T4 | C++ | 通过 | 100 | 111 MS | 4160 KB | 714 | 2025-10-03 15:45:56 |
#include<bits/stdc++.h> using namespace std; int n; long long M=998244353; int f[200005],g[200005]; int dp[200005]; struct wsw{ int a,b; }num[200005]; int p[200005]; bool cmp(wsw x,wsw y){ return x.a<y.a; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>num[i].a>>num[i].b; } sort(num+1,num+n+1,cmp); for(int i=1;i<=n;i++){ int l=i,r=n,t=num[i].a+num[i].b; while(l<r){ int mid=(l+r+1)/2; if(t>num[mid].a) l=mid; if(t<=num[mid].a) r=mid-1; } f[i]=l; } for(int i=n;i>=1;i--){ g[i]=f[i]; for(int j=i+1;j<=f[i];j++){ g[i]=max(g[i],g[j]); } } dp[n+1]=1; for(int i=n;i>=1;i--){ dp[i]=(dp[i+1]+dp[g[i]+1])%M; } cout<<dp[1]; return 0; }