Submission #1086497

#TimeUsernameProblemLanguageResultExecution timeMemory
1086497PikachudoraEHETrains (BOI24_trains)C++14
0 / 100
117 ms124980 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5+5;const int ee = 1e9+7; vector<int>adj[N];long long dp[N];int d[N],x[N]; long long qs[500][N]; /*struct fenwick{ long long f[4*N]; void update(int idx,long long v){ for(int i=idx;i<N;i+=i&-i){ f[i]+=v; } return; } long long sum(int idx){ long long s = 0; for(int i=idx;i>=0;i-=i&-i){ s+=f[i]; s%=ee; } return s; } }qs[400];*/ int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n;int k = 1; while(k*k<N){ k++; } for(int i=1;i<=n;i++){ cin>>d[i]>>x[i]; if(d[i]>k){ int cnt = min(((n-i)/d[i]),x[i]); for(int ii=1;ii<=cnt;ii++){ adj[((ii*d[i])+i)].push_back(i); } } } dp[1]=1;long long ans=0; for(int i=1;i<=n;i++){ if(d[i]<=k&&d[i]>0){ qs[d[i]][i]+=dp[i]; qs[d[i]][i]%=ee; //cout<<"1 "<<qs[d[i]][i]<<" = "<<qs[d[i]][i]-dp[i]<<" + "<<dp[i]<<"\n"; //qs[d[i]][i]+=qs[d[i]][i-d[i]]; //cout<<"2 "<<qs[d[i]][i]<<" = "<<qs[d[i]][i]-qs[d[i]][i-d[i]]<<" + "<<qs[d[i]][i-d[i]]<<"\n"; int cnt = min(((n-i)/d[i]),x[i])-1; qs[d[i]][((cnt*d[i])+i+d[i])]-=dp[i]; qs[d[i]][((cnt*d[i])+i+d[i])]%=ee; //cout<<" "<<(cnt*d[i])+i+d[i]<<" "<<qs[d[i]][(cnt*d[i])+i+d[i]]<<" = "<<qs[d[i]][(cnt*d[i])+i+d[i]]+dp[i]<<" - "<<dp[i]<<"\n"; } for(auto v:adj[i+1]){ dp[i+1]+=dp[v]; dp[i+1]%=ee; } for(int ii=1;ii<=k;ii++){ qs[ii][i+1]+=qs[ii][i+1-ii]; qs[ii][i+1]%=ee; dp[i+1]+=qs[ii][i+1]; dp[i+1]%=ee; //dp[i+1]+=qs[ii][i+1-ii]; //cout<<"4 "<<dp[i+1]<<" = "<<dp[i+1]-qs[ii][i+1-ii]<<" + "<<qs[ii][i+1-ii]<<"\n"; //dp[i+1]%=ee; } ans+=dp[i]; //cout<<dp[i]<<"\n"; ans%=ee; } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...