Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38365 22级廖思学 【S】T4 C++ 通过 100 142 MS 10608 KB 1556 2025-10-03 15:35:52

Tests(10/10):


#include<bits/stdc++.h> using namespace std; #define int long long #define ls pos<<1 #define rs pos<<1|1 const int N=2e5+10,M=998244353; int n,nx[N],t[N<<2],f[N]; struct Pai{int a,b;}c[N]; void pushup(int pos){t[pos]=max(t[ls],t[rs]);} void build(int pos,int l,int r){ if(l==r){t[pos]=nx[l];return;} int mid=(l+r)>>1; build(ls,l,mid);build(rs,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int x,int k){ if(l==r){t[pos]=k;return;} int mid=(l+r)>>1; if(x<=mid)update(ls,l,mid,x,k); else update(rs,mid+1,r,x,k); pushup(pos); } int query(int pos,int l,int r,int ql,int qr){ if(l>=ql&&r<=qr){return t[pos];} int mid=(l+r)>>1,res=0; if(ql<=mid)res=query(ls,l,mid,ql,qr); if(qr>mid)res=max(res,query(rs,mid+1,r,ql,qr)); return res; } bool cmp(Pai x,Pai y){return x.a<y.a;} signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++)scanf("%lld%lld",&c[i].a,&c[i].b); sort(c+1,c+n+1,cmp); for(int i=1;i<=n;i++){ int l=i,r=n; while(l<r){ int mid=(l+r+1)>>1; if(c[mid].a<c[i].a+c[i].b)l=mid; else r=mid-1; } nx[i]=l; } build(1,1,n); for(int i=n;i>=1;i--){ nx[i]=query(1,1,n,i,nx[i]); update(1,1,n,i,nx[i]); } // for(int i=1;i<=n;i++)cout<<nx[i]<<" ";cout<<endl; f[n+1]=1; for(int i=n;i>=1;i--){ f[i]=(f[i+1]+f[nx[i]+1])%M; // cout<<f[i]<<" "; }//cout<<endl; printf("%lld\n",f[1]); return 0; }


测评信息: