Submission #1366508

#TimeUsernameProblemLanguageResultExecution timeMemory
1366508SofiatpcTrains (BOI24_trains)C++20
42 / 100
94 ms3508 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 1e5+5, RZ = 316, MOD = 1e9+7;
int d[MAXN], x[MAXN], sum[RZ+5][RZ+5], dp[MAXN];
vector< pair<int,int> > e;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>d[i]>>x[i];

        if(d[i] != 0 && d[i] < RZ && i+d[i]*(x[i]+1) <= n)e.emplace_back( i+d[i]*(x[i]+1), i);

        dp[i] = 1;
    }

    sort(e.begin(),e.end());

    for(int i = n; i >= 1; i--){
        if(d[i] != 0 && d[i] < RZ)dp[i] = (dp[i] + sum[ d[i] ][ i%d[i] ])%MOD;
        if(d[i] != 0 && d[i] >= RZ){
            for(int j = i+d[i]; j <= min(i+d[i]*x[i], n); j += d[i]) dp[i] = (dp[i] + dp[j])%MOD;
        }

        for(int j = 1; j < RZ; j++)sum[ j ][ i%j ] = (sum[ j ][ i%j ] + dp[i])%MOD;

        while(sz(e) > 0 && e.back().fi == i){
            int id = e.back().sc;
            dp[id] -= sum[ d[id] ][ id%d[id] ];
            e.pop_back();
        }
    }

    cout<<dp[1]<<"\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...