Submission #1086493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086493		PikachudoraEHE	Trains (BOI24_trains)	C++14	42 / 100	239 ms	254544 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long N = 1e5+5;const long long ee = 1e9+7;
vector<long long>adj[N];long long dp[N];long long d[N],x[N];
long long qs[500][N];
/*struct fenwick{
    long long f[4*N];
    void update(long long idx,long long v){
        for(long long i=idx;i<N;i+=i&-i){
            f[i]+=v;
        }
    return;
    }
    long long sum(long long idx){
        long long s = 0;
        for(long long 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);
    long long n;cin>>n;long long k = 1;
    while(k*k<N){
        k++;
    }
    for(long long i=1;i<=n;i++){
        cin>>d[i]>>x[i];
        if(d[i]>k){
            long long cnt = (n-i)/d[i];
            if(cnt>x[i])cnt = x[i];
            for(long long ii=1;ii<=cnt;ii++){
                adj[((ii*d[i])+i)].push_back(i);
            }
        }
    }
    dp[1]=1;long long ans=0;
    for(long long 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";
            long long cnt = (n-i)/d[i];
            if(cnt>x[i])cnt = x[i];
            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(long long 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: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 34 / 34
• Subtask 5: 0 / 29