oj.uz

Submission #1086493

# Submission time Handle Problem Language Result Execution time Memory
1086493 2024-09-10T18:50:22 Z PikachudoraEHE Trains (BOI24_trains) C++14
42 / 100
 239 ms 254544 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 3 ms 4468 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 3 ms 4612 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 3 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 3 ms 4440 KB Output is correct
18 Correct 3 ms 4484 KB Output is correct
19 Correct 4 ms 4444 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 3 ms 4468 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 3 ms 4612 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 3 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 3 ms 4440 KB Output is correct
18 Correct 3 ms 4484 KB Output is correct
19 Correct 4 ms 4444 KB Output is correct
20 Incorrect 26 ms 25180 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 18 ms 20728 KB Output is correct
3 Incorrect 14 ms 15788 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 125524 KB Output is correct
2 Correct 98 ms 104932 KB Output is correct
3 Correct 239 ms 254444 KB Output is correct
4 Correct 173 ms 184404 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 26 ms 29580 KB Output is correct
8 Correct 239 ms 254544 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 3 ms 4468 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 3 ms 4612 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 3 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 3 ms 4440 KB Output is correct
18 Correct 3 ms 4484 KB Output is correct
19 Correct 4 ms 4444 KB Output is correct
20 Incorrect 26 ms 25180 KB Output isn't correct
21 Halted 0 ms 0 KB -