Submission #1033297

#TimeUsernameProblemLanguageResultExecution timeMemory
1033297borisAngelovTrains (BOI24_trains)C++17
34 / 100
103 ms5936 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const int BLOCK_SIZE = 355; const int mod = 1e9 + 7; int n; int d[maxn], x[maxn]; int dp[maxn]; int pref[maxn]; int prefSmall[BLOCK_SIZE][BLOCK_SIZE]; vector<pair<int, int>> toRemove[maxn]; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n; for (int i = 1; i <= n; ++i) { cin >> d[i] >> x[i]; } int big = sqrt(n); int ans = 0; for (int i = 1; i <= n; ++i) { for (auto [small, value] : toRemove[i]) { for (int j = 0; j < small; ++j) { prefSmall[small][j] -= value; if (prefSmall[small][j] < 0) prefSmall[small][j] += mod; } } if (i == 1) { dp[i] = 1; } else { for (int small = 1; small < big; ++small) { dp[i] += prefSmall[small][i % small]; if (dp[i] >= mod) dp[i] -= mod; } } if (d[i] >= big) { for (int j = i + d[i]; j <= n; j += d[i]) { dp[j] += dp[i]; if (dp[j] >= mod) dp[j] -= mod; } } else if (d[i] != 0) { prefSmall[d[i]][i % d[i]] += dp[i]; if (prefSmall[d[i]][i % d[i]] >= mod) prefSmall[d[i]][i % d[i]] -= mod; } ans += dp[i]; if (ans >= mod) ans -= mod; if (d[i] != 0) { toRemove[min(1LL * n + 1LL, i + (1LL * x[i]) * (1LL * d[i]) + 1LL)].push_back({d[i], dp[i]}); } //cout << i << " :: " << dp[i] << endl; } cout << ans << endl; return 0; } /* 5 1 3 1 1 1 2 1 2 1 2 2 :: 1 3 :: 2 4 :: 3 5 :: 5 12 3 1000000000 5 1000000000 2 1000000000 7 1000000000 4 1000000000 1 1000000000 1 1000000000 5 1000000000 2 1000000000 1 1000000000 1 1000000000 3 1000000000 here 2 :: 0 here 3 :: 0 here 4 :: 1 here 5 :: 0 here 6 :: 0 here 7 :: 1 here 8 :: 1 here 9 :: 1 here 10 :: 2 here 11 :: 5 here 12 :: 8 */
#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...