Submission #1235892

#TimeUsernameProblemLanguageResultExecution timeMemory
1235892rhm_ganTrains (BOI24_trains)C++20
21 / 100
118 ms2116 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define dbg(...) 42 #endif 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 (l > r) return 0; 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; } int 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]); int x = query(0, 0, n - 1, l, r); update(0, 0, n - 1, i, x); } cout << query(0, 0, n - 1, 0, 0) << '\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...