| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 994566 |
2024-06-08T01:27:55 Z |
pavement |
Trains (BOI24_trains) |
C++17 |
|
891 ms |
381100 KB |
#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)) % MOD + MOD) % MOD;
}
}
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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3176 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 7 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 8 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 9 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 11 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 12 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 13 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 14 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 15 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 16 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 17 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 18 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 19 |
Correct |
1 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3176 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 7 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 8 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 9 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 11 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 12 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 13 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 14 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 15 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 16 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 17 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 18 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 19 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 20 |
Incorrect |
94 ms |
68156 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Incorrect |
67 ms |
53756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
891 ms |
381100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3176 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 7 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 8 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 9 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 11 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 12 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 13 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 14 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 15 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 16 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 17 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 18 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 19 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 20 |
Incorrect |
94 ms |
68156 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
