제출 #994565

#제출 시각아이디문제언어결과실행 시간메모리
994565pavementTrains (BOI24_trains)C++17
8 / 100
705 ms381008 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back const int MOD = (int)1e9 + 7, LIM = 316, LIM2 = 316; int N, d[100005], x[100005], dp[100005], sf[LIM2 + 5][LIM2]; vector<int> ft[LIM2 + 5][LIM2]; int ls(int x) { return x & -x; } void ft_upd(vector<int> &ft, int pos, int v) { for (; pos <= (int)ft.size(); pos += ls(pos)) { ft[pos - 1] = (ft[pos - 1] + v) % MOD; } } int ft_qry(vector<int> &ft, int pos) { int ret = 0; for (; pos; pos -= ls(pos)) { ret = (ret + ft[pos - 1]) % MOD; } return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 1; i <= N; i++) { cin >> d[i] >> x[i]; } for (int j = 1; j <= LIM2; j++) { for (int k = 0; k < LIM2; k++) { // i % j == k // i = k + j * t (t >= 0) // k + j * t <= N // t <= (N - k) / j int cnt = max(0, (N - k) / j); ft[j][k].resize(cnt); } } for (int i = N; i >= 1; i--) { if (d[i]) { int num_stops = min(x[i], (N - i) / d[i]); if (num_stops <= LIM) { for (int j = 1; j <= num_stops; j++) { dp[i] = (dp[i] + dp[i + j * d[i]]) % MOD; } } else { assert(d[i] <= LIM2); dp[i] = ft_qry(ft[d[i]][i % d[i]], ft[d[i]][i % d[i]].size()) - ft_qry(ft[d[i]][i % d[i]], sf[d[i]][i % d[i]] - num_stops + 1); } } dp[i] = (dp[i] + 1) % MOD; for (int j = 1; j <= LIM2; j++) { ft_upd(ft[j][i % j], ++sf[j][i % j], dp[i]); } } cout << dp[1] << '\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...