Submission #1179301

#TimeUsernameProblemLanguageResultExecution timeMemory
1179301gygTrains (BOI24_trains)C++20
34 / 100
175 ms9376 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vec vector 
const int N = 1e5 + 5, K = 325, MD = 1e9 + 7;

int n;
arr<int, N> d, s;

int md(int x) { return (x + MD) % MD; }
arr<int, N> dp;

arr<arr<int, K>, K> add;
arr<vec<vec<int>>, N> rmv;

void cmp() {
    for (int i = 1; i <= n; i++) {
        if (i == 1) dp[i] = 1;
        else {
            for (int j = 1; j <= 320; j++) {
                dp[i] = md(dp[i] + add[j][i % j]);
            }
        }

        for (vec<int> x : rmv[i]) {
            add[x[0]][x[1]] = md(add[x[0]][x[1]] - x[2]);
        }
        if (!d[i]) continue;

        if (d[i] <= 320) {
            add[d[i]][i % d[i]] = md(add[d[i]][i % d[i]] + dp[i]);
            if (i + s[i] * d[i] <= n) {
                rmv[i + s[i] * d[i]].push_back({d[i], i % d[i], dp[i]});
            }
        } else {
            for (int j = i + d[i]; j <= min(i + s[i] * d[i], n); j += d[i]) {
                dp[j] = md(dp[j] + dp[i]);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) ans = md(ans + dp[i]);
    cout << ans << '\n';
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i] >> s[i];

    cmp();
}
#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...