# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
994567 |
2024-06-08T01:30:23 Z |
pavement |
Trains (BOI24_trains) |
C++17 |
|
1878 ms |
789336 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) {
//~ cout << "UPD " << pos << ' ' << v << '\n';
for (; pos <= (int)ft.size(); pos += ls(pos)) {
ft[pos - 1] = (ft[pos - 1] + v) % MOD;
}
}
int ft_qry(vector<int> &ft, int pos) {
//~ cout << "QU " << pos << '\n';
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)) % 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 |
3164 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 |
3164 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 |
3160 KB |
Output is correct |
12 |
Correct |
1 ms |
3160 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 |
3112 KB |
Output is correct |
17 |
Correct |
1 ms |
3160 KB |
Output is correct |
18 |
Correct |
2 ms |
3160 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 |
3164 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 |
3164 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 |
3160 KB |
Output is correct |
12 |
Correct |
1 ms |
3160 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 |
3112 KB |
Output is correct |
17 |
Correct |
1 ms |
3160 KB |
Output is correct |
18 |
Correct |
2 ms |
3160 KB |
Output is correct |
19 |
Correct |
1 ms |
3164 KB |
Output is correct |
20 |
Correct |
87 ms |
68304 KB |
Output is correct |
21 |
Correct |
28 ms |
26424 KB |
Output is correct |
22 |
Correct |
108 ms |
81488 KB |
Output is correct |
23 |
Correct |
65 ms |
53852 KB |
Output is correct |
24 |
Correct |
38 ms |
35328 KB |
Output is correct |
25 |
Correct |
97 ms |
73308 KB |
Output is correct |
26 |
Correct |
44 ms |
38236 KB |
Output is correct |
27 |
Correct |
92 ms |
69972 KB |
Output is correct |
28 |
Correct |
109 ms |
81496 KB |
Output is correct |
29 |
Correct |
110 ms |
81492 KB |
Output is correct |
30 |
Correct |
108 ms |
81604 KB |
Output is correct |
31 |
Correct |
106 ms |
81500 KB |
Output is correct |
32 |
Correct |
106 ms |
81500 KB |
Output is correct |
33 |
Correct |
106 ms |
81500 KB |
Output is correct |
34 |
Correct |
105 ms |
81752 KB |
Output is correct |
35 |
Correct |
103 ms |
81492 KB |
Output is correct |
36 |
Correct |
109 ms |
81496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3164 KB |
Output is correct |
2 |
Correct |
64 ms |
53936 KB |
Output is correct |
3 |
Correct |
43 ms |
38232 KB |
Output is correct |
4 |
Correct |
84 ms |
69972 KB |
Output is correct |
5 |
Correct |
1158 ms |
610644 KB |
Output is correct |
6 |
Correct |
1687 ms |
789336 KB |
Output is correct |
7 |
Correct |
1750 ms |
789328 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 |
100 ms |
81584 KB |
Output is correct |
12 |
Correct |
1780 ms |
789332 KB |
Output is correct |
13 |
Correct |
1 ms |
3160 KB |
Output is correct |
14 |
Correct |
108 ms |
81492 KB |
Output is correct |
15 |
Correct |
1726 ms |
789324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
750 ms |
381096 KB |
Output is correct |
2 |
Correct |
545 ms |
317272 KB |
Output is correct |
3 |
Correct |
1761 ms |
789328 KB |
Output is correct |
4 |
Correct |
1046 ms |
565328 KB |
Output is correct |
5 |
Correct |
1 ms |
3164 KB |
Output is correct |
6 |
Correct |
1 ms |
3164 KB |
Output is correct |
7 |
Correct |
106 ms |
81448 KB |
Output is correct |
8 |
Correct |
1784 ms |
789336 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 |
3164 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 |
3164 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 |
3160 KB |
Output is correct |
12 |
Correct |
1 ms |
3160 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 |
3112 KB |
Output is correct |
17 |
Correct |
1 ms |
3160 KB |
Output is correct |
18 |
Correct |
2 ms |
3160 KB |
Output is correct |
19 |
Correct |
1 ms |
3164 KB |
Output is correct |
20 |
Correct |
87 ms |
68304 KB |
Output is correct |
21 |
Correct |
28 ms |
26424 KB |
Output is correct |
22 |
Correct |
108 ms |
81488 KB |
Output is correct |
23 |
Correct |
65 ms |
53852 KB |
Output is correct |
24 |
Correct |
38 ms |
35328 KB |
Output is correct |
25 |
Correct |
97 ms |
73308 KB |
Output is correct |
26 |
Correct |
44 ms |
38236 KB |
Output is correct |
27 |
Correct |
92 ms |
69972 KB |
Output is correct |
28 |
Correct |
109 ms |
81496 KB |
Output is correct |
29 |
Correct |
110 ms |
81492 KB |
Output is correct |
30 |
Correct |
108 ms |
81604 KB |
Output is correct |
31 |
Correct |
106 ms |
81500 KB |
Output is correct |
32 |
Correct |
106 ms |
81500 KB |
Output is correct |
33 |
Correct |
106 ms |
81500 KB |
Output is correct |
34 |
Correct |
105 ms |
81752 KB |
Output is correct |
35 |
Correct |
103 ms |
81492 KB |
Output is correct |
36 |
Correct |
109 ms |
81496 KB |
Output is correct |
37 |
Correct |
1 ms |
3164 KB |
Output is correct |
38 |
Correct |
64 ms |
53936 KB |
Output is correct |
39 |
Correct |
43 ms |
38232 KB |
Output is correct |
40 |
Correct |
84 ms |
69972 KB |
Output is correct |
41 |
Correct |
1158 ms |
610644 KB |
Output is correct |
42 |
Correct |
1687 ms |
789336 KB |
Output is correct |
43 |
Correct |
1750 ms |
789328 KB |
Output is correct |
44 |
Correct |
1 ms |
3160 KB |
Output is correct |
45 |
Correct |
1 ms |
3164 KB |
Output is correct |
46 |
Correct |
1 ms |
3164 KB |
Output is correct |
47 |
Correct |
100 ms |
81584 KB |
Output is correct |
48 |
Correct |
1780 ms |
789332 KB |
Output is correct |
49 |
Correct |
1 ms |
3160 KB |
Output is correct |
50 |
Correct |
108 ms |
81492 KB |
Output is correct |
51 |
Correct |
1726 ms |
789324 KB |
Output is correct |
52 |
Correct |
750 ms |
381096 KB |
Output is correct |
53 |
Correct |
545 ms |
317272 KB |
Output is correct |
54 |
Correct |
1761 ms |
789328 KB |
Output is correct |
55 |
Correct |
1046 ms |
565328 KB |
Output is correct |
56 |
Correct |
1 ms |
3164 KB |
Output is correct |
57 |
Correct |
1 ms |
3164 KB |
Output is correct |
58 |
Correct |
106 ms |
81448 KB |
Output is correct |
59 |
Correct |
1784 ms |
789336 KB |
Output is correct |
60 |
Correct |
1482 ms |
658260 KB |
Output is correct |
61 |
Correct |
1869 ms |
789328 KB |
Output is correct |
62 |
Correct |
1771 ms |
789308 KB |
Output is correct |
63 |
Correct |
1746 ms |
789336 KB |
Output is correct |
64 |
Correct |
1696 ms |
789316 KB |
Output is correct |
65 |
Correct |
1802 ms |
789328 KB |
Output is correct |
66 |
Correct |
1787 ms |
789236 KB |
Output is correct |
67 |
Correct |
1718 ms |
789144 KB |
Output is correct |
68 |
Correct |
1748 ms |
789148 KB |
Output is correct |
69 |
Correct |
1878 ms |
789332 KB |
Output is correct |
70 |
Correct |
1734 ms |
789324 KB |
Output is correct |
71 |
Correct |
1702 ms |
789272 KB |
Output is correct |
72 |
Correct |
1744 ms |
789244 KB |
Output is correct |