제출 #1298721

#제출 시각아이디문제언어결과실행 시간메모리
1298721kawhietTrains (BOI24_trains)C++20
37 / 100
125 ms5232 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int mod = 1e9 + 7;
 
vector<int> st;
 
void build(int id, int tl, int tr) {
    if (tl == tr) {
        st[id] = 1;
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    build(x, tl, tm);
    build(y, tm + 1, tr);
    st[id] = st[x] + st[y];
}
 
void update(int id, int tl, int tr, int i, int v) {
    if (tl == tr) {
        st[id] = (st[id] + v) % mod;
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    if (i <= tm)
        update(x, tl, tm, i, v);
    else
        update(y, tm + 1, tr, i, v);
    st[id] = st[x] + st[y];
}
 
int query(int id, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return 0;
    if (l <= tl && tr <= r) return st[id] % mod;
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    return (query(x, tl, tm, l, r) + query(y, tm + 1, tr, l, r)) % mod;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> d(n), a(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> a[i];
    }
    if (n <= 1e4) {
        vector<int> dp(n + 1, 1);
        for (int i = n - 1; i >= 0; i--) {
            int x = i;
            if (d[i] == 0) continue;
            for (int j = 0; j < a[i]; j++) {
                x += d[i];
                if (x >= n) break;
                dp[i] += dp[x];
                if (dp[i] > mod) {
                    dp[i] -= mod;
                }
            }
        }
        cout << dp[0] << '\n';
        return 0;
    }
    st.resize(4 * n);
    build(0, 0, n - 1);
    for (int i = n - 1; i >= 0; i--) {
        int l = i + 1, r = min(n, i + a[i]);
        if (l > r) continue;
        int x = query(0, 0, n - 1, l, r) % mod;
        update(0, 0, n - 1, i, x);
    }
    cout << query(0, 0, n - 1, 0, 0) % mod << '\n';
    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...