Submission #1243829

#TimeUsernameProblemLanguageResultExecution timeMemory
1243829lopkusTrains (BOI24_trains)C++20
8 / 100
701 ms176012 KiB
#include <bits/stdc++.h> #define int long long int mod = 1e9 + 7; int add(int x, int y) { x += y; x %= mod; return x; } int S = 280; const int N = 1e5 + 5; struct fenwick { int t[2 * N]; int query(int i) { int ans = 0; for(; i > 0; i -= i & - i) { ans = add(ans, t[i]); } return ans; } int query(int l, int r) { return query(r) - query(l - 1); } void update(int i, int v) { for(; i < N; i += i & - i) { t[i] = add(t[i], v); } } void update(int l, int r, int v) { update(l, v); update(r + 1, - v); } }fenwick[281]; signed main() { int n; std::cin >> n; std::vector<int> d(n + 1), x(n + 1); for(int i = 1; i <= n; i++) { std::cin >> d[i] >> x[i]; } std::vector<int> dp(n + 1, 0); dp[1] = 1; std::vector<std::vector<int>> pref(n + 1, std::vector<int>(S)); for(int i = 1; i <= n; i++) { if(d[i] == 0) { continue; } int e = (n - i + 1) / d[i]; for(int t = 1; t < S; t++) { if(i - t >= 0) { dp[i] = add(dp[i], fenwick[t].query(i)); } } if(d[i] >= S) { for(int t = 1; t <= x[i] && i + t * d[i] <= n; t++) { dp[i + t * d[i]] = add(dp[i + t * d[i]], dp[i]); } } else { if(e <= S) { for(int t = 1; t <= x[i] && i + t * d[i] <= n; t++) { dp[i + t * d[i]] = add(dp[i + t * d[i]], dp[i]); } } else { int w = std::min(n, i + x[i] * d[i]); fenwick[d[i]].update(i, w, dp[i]); } } } int ans = 0; for(int i = 1; i <= n; i++) { ans = add(ans, dp[i]); } std::cout << ans; }
#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...