Submission #1086505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086505		PikachudoraEHE	Trains (BOI24_trains)	C++14	100 / 100	383 ms	297304 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;const int ee = 1e9+7;
vector<int>adj[2*N];long long dp[N];int d[N],x[N];
long long qs[500][2*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]);
            qs[d[i]][((cnt*d[i])+i+d[i])]+=(ee-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;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29