Submission #1084754

#TimeUsernameProblemLanguageResultExecution timeMemory
1084754zxciganTrains (BOI24_trains)C++17
34 / 100
184 ms9812 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long const int N = 2e5; const int mod = 1e9 + 7; const int B = 335; int dp[N]; int32_t main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; dp[1] = 1; int s = 0; vector<vector<int>> add (B + 1, vector<int> (B + 1, 0)); set<array<int,4>> st; for (int i = 1; i <= n; ++i) { int x, d; cin >> d >> x; for (int j = 1; j < B; ++j) { (dp[i] += add[j][i % j]) %= mod; } if (x && d) { if (d >= B) { for (int j = 1; j <= x; ++j) { if (i + d * j > n) break; (dp[i + d * j] += dp[i]) %= mod; } } else { (add[d][i % d] += dp[i]) %= mod; st.insert ({i + x * d + 1, d, i % d, dp[i]}); } } while ((int)st.size() && (*st.begin())[0] == i) { array<int,4> v = (*st.begin()); add[v[1]][v[2]] -= v[3]; while (add[v[1]][v[2]] < 0) add[v[1]][v[2]] += mod; st.erase (st.begin()); } (s += dp[i]) %= mod; } cout << s << '\n'; }
#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...