Submission #1297570

#TimeUsernameProblemLanguageResultExecution timeMemory
1297570matematteoTrains (BOI24_trains)C++20
16 / 100
239 ms256692 KiB
// NOTE: it is recommended to use this even if you don't understand the
// following code.

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
const long long mod=1e9+7;
struct nd{
    long long d, x;
    vector<long long>sus;
    vector<long long>flag;
};
int main() {
    #define int long long
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, Q;
    cin >> N;
    int d=sqrt(N);
    vector<long long>dp(N);
    vector<nd>t(N);
    for (int a,b,i=0;i<N;i++){
        cin >> a >> b;
        t[i].d=a; t[i].x=min(N,b);
        t[i].sus.resize(d);
    }
    dp[0]=1;
    long long sum=0;
    for (int i=0;i<N;i++){
        for (int j=0;j<d;j++){
            dp[i]+=t[i].sus[j];
            dp[i]%=mod;
        }
        if (t[i].d>=d){
            int j=i;
            j+=t[i].d;
            int s=1;
            while (j<N&&s<=t[i].x){
                dp[j]+=dp[i];
                dp[j]%=mod;
                j+=t[i].d;
                s++;
            }
        }
        else{
            if (i+t[i].d*t[i].x<N){
                t[i+t[i].d*t[i].x].flag.push_back(i);
            }
            t[i].sus[t[i].d]+=dp[i]; t[i].sus[t[i].d]%=mod;
        }
        for (auto u:t[i].flag){
            t[i].sus[t[u].d]-=dp[u]; t[i].sus[t[u].d]+=mod; t[i].sus[t[u].d]%=mod;
        }
        if (i!=N-1){
            t[i+1].sus=t[i].sus;
        }
        sum+=dp[i]; sum%=mod;
    }
    //for (int i=0;i<N;i++) cout << dp[i] << " "; cout << endl;
    cout << sum;
    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...