제출 #1033933

#제출 시각아이디문제언어결과실행 시간메모리
1033933cnn008Trains (BOI24_trains)C++17
21 / 100
150 ms8144 KiB
#include "bits/stdc++.h" using namespace std; #ifdef N_N_C #include "debug.h" #else #define cebug(...) "Arya" #endif #define int long long const int N=1e5+5; const int mod=1e9+7; const int sz=320; int n,d[N],x[N],en[N]; vector <pair <int,int> > v[N]; namespace sub1{ bool ck(){ return n<=10000; } int dp[N]; void sol(){ dp[1]=1; for(int i=2; i<=n; i++){ for(int j=1; j<i; j++){ if(d[j] and (i-j)%d[j]==0 and en[j]>=i) dp[i]=(dp[i]+dp[j]<mod?dp[i]+dp[j]:dp[i]+dp[j]-mod); } } int ans=0; for(int i=1; i<=n; i++) ans=(ans+dp[i]<mod?ans+dp[i]:ans+dp[i]-mod); cout<<ans; } } namespace sub2{ bool ck(){ for(int i=1; i<=n; i++) if(d[i]!=1) return 0; return 1; } struct BIT{ #define gb(x) (x)&(-x) int n; vector <int> bit; void init(int _n){ n=_n; bit.resize(_n,0); } void update(int i, int v){ for(; i<n; i+=gb(i)) bit[i]=(bit[i]+v)%mod; } void range(int l, int r, int v){ if(l>r) return; update(l,v); update(r+1,-v); } int get(int i){ int ans=0; for(; i; i-=gb(i)) ans=(ans+bit[i])%mod; return ans; } }fw; int dp[N]; void sol(){ fw.init(n+5); dp[1]=1; fw.range(2,en[2],1); int ans=1; for(int i=2; i<=n; i++){ dp[i]=(fw.get(i)-fw.get(i-1)+mod)%mod; fw.range(i+1,en[i],dp[i]); ans=(ans+dp[i])%mod; } cout<<ans; } } namespace full{ int dp[N],g[sz+5][sz+5],ans; void sol(){ dp[1]=1; for(int i=1; i<=n; i++){ for(int j=1; j<=sz; j++){ dp[i]=(dp[i]+g[j][i%j])%mod; } if(d[i]>sz){ for(int j=i+d[i]; j<=en[i]; j+=d[i]) dp[j]=(dp[j]+dp[i])%mod; }else if(d[i]>0){ g[d[i]][i%d[i]]=(g[d[i]][i%d[i]]+dp[i])%mod; } for(auto [j,_d]:v[i]) if(_d<=sz) g[_d][j%_d]=(g[_d][j%_d]-dp[j]+mod)%mod; } for(int i=1; i<=n; i++) ans=(ans+dp[i])%mod; cout<<ans; } } void sol(){ cin>>n; for(int i=1; i<=n; i++) cin>>d[i]>>x[i],en[i]=min(n,i+d[i]*x[i]); for(int i=1; i<=n; i++) if(d[i] and d[i]<=sz) v[en[i]].push_back({i,d[i]}); if(sub1::ck()){ sub1::sol(); return; } if(sub2::ck()){ sub2::sol(); return; } full::sol(); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("arya.inp", "r", stdin); // freopen("arya.out", "w", stdout); int tt=1; //cin>>tt; while(tt--){ sol(); } cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; 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...