#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "dungeons.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e5 + 10;
int n;
int s[N], p[N], w[N], l[N];
int nxt[N][7][25];
long long dmin[N][7][25];
long long sum[N][7][25];
vector <long long> pivot;
void init(int _n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = _n;
for (int i = 0; i < n; ++i) s[i] = S[i], p[i] = P[i], w[i] = W[i], l[i] = L[i];
for (int i = 0; i < 7; ++i) pivot.push_back(1 << i * 4);
pivot.push_back(1e18);
for (int b = 0; b + 1 < pivot.size(); ++b) {
for (int i = 0; i < n; ++i) {
if (s[i] <= pivot[b]) {
nxt[i][b][0] = w[i];
dmin[i][b][0] = 1e18;
sum[i][b][0] = s[i];
} else {
nxt[i][b][0] = l[i];
dmin[i][b][0] = s[i];
sum[i][b][0] = p[i];
}
}
nxt[n][b][0] = n;
for (int lg = 1; lg < 25; ++lg) {
for (int i = 0; i <= n; ++i) {
nxt[i][b][lg] = nxt[nxt[i][b][lg - 1]][b][lg - 1];
sum[i][b][lg] = sum[i][b][lg - 1] + sum[nxt[i][b][lg - 1]][b][lg - 1];
dmin[i][b][lg] = min(dmin[i][b][lg - 1], dmin[nxt[i][b][lg - 1]][b][lg - 1] - sum[i][b][lg - 1]);
}
}
}
}
long long simulate(int i, int z) {
long long cur = z;
int b = 0;
while (b + 1 < pivot.size()) {
if (cur >= pivot[b + 1]) {
++b;
continue;
}
for (int lg = 24; lg >= 0; --lg) {
if (nxt[i][b][lg] == n || dmin[i][b][lg] - cur <= 0) continue;
cur += sum[i][b][lg];
i = nxt[i][b][lg];
}
if (cur >= s[i]) {
cur += s[i];
i = w[i];
} else {
cur += p[i];
i = l[i];
}
if (i == n) return cur;
}
return cur;
}
//int main() {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// int n, q;
// std::vector<int> s, p, z;
// std::vector<int> w, l, x;
// std::vector<long long> answer;
//
// assert(scanf("%d %d", &n, &q) == 2);
// s.resize(n);
// p.resize(n);
// w.resize(n);
// l.resize(n);
// x.resize(q);
// z.resize(q);
// answer.resize(q);
//
// for (int i = 0; i < n; i++) {
// assert(scanf("%d", &s[i]) == 1);
// }
// for (int i = 0; i < n; i++) {
// assert(scanf("%d", &p[i]) == 1);
// }
// for (int i = 0; i < n; i++) {
// assert(scanf("%d", &w[i]) == 1);
// }
// for (int i = 0; i < n; i++) {
// assert(scanf("%d", &l[i]) == 1);
// }
//
//
// init(n, s, p, w, l);
//
// for (int i = 0; i < q; i++) {
// assert(scanf("%d %d", &x[i], &z[i]) == 2);
// answer[i] = simulate(x[i], z[i]);
// }
// fclose(stdin);
//
// for (int i = 0; i < q; i++) {
// printf("%lld\n", answer[i]);
// }
// fclose(stdout);
// return 0;
//}
Compilation message
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int b = 0; b + 1 < pivot.size(); ++b) {
| ~~~~~~^~~~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while (b + 1 < pivot.size()) {
| ~~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
6 ms |
7252 KB |
Output is correct |
4 |
Correct |
336 ms |
175156 KB |
Output is correct |
5 |
Correct |
7 ms |
7252 KB |
Output is correct |
6 |
Correct |
383 ms |
174844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3792 KB |
Output is correct |
2 |
Correct |
3204 ms |
1391124 KB |
Output is correct |
3 |
Correct |
3150 ms |
1389692 KB |
Output is correct |
4 |
Correct |
3016 ms |
1389940 KB |
Output is correct |
5 |
Correct |
3154 ms |
1389756 KB |
Output is correct |
6 |
Correct |
3235 ms |
1389924 KB |
Output is correct |
7 |
Correct |
2969 ms |
1389752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3796 KB |
Output is correct |
2 |
Correct |
413 ms |
174720 KB |
Output is correct |
3 |
Correct |
396 ms |
174908 KB |
Output is correct |
4 |
Correct |
356 ms |
175812 KB |
Output is correct |
5 |
Correct |
385 ms |
175724 KB |
Output is correct |
6 |
Correct |
381 ms |
176072 KB |
Output is correct |
7 |
Correct |
402 ms |
175984 KB |
Output is correct |
8 |
Correct |
360 ms |
175680 KB |
Output is correct |
9 |
Correct |
359 ms |
175608 KB |
Output is correct |
10 |
Correct |
391 ms |
175676 KB |
Output is correct |
11 |
Correct |
427 ms |
175948 KB |
Output is correct |
12 |
Correct |
546 ms |
175968 KB |
Output is correct |
13 |
Correct |
400 ms |
175948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3796 KB |
Output is correct |
2 |
Correct |
413 ms |
174720 KB |
Output is correct |
3 |
Correct |
396 ms |
174908 KB |
Output is correct |
4 |
Correct |
356 ms |
175812 KB |
Output is correct |
5 |
Correct |
385 ms |
175724 KB |
Output is correct |
6 |
Correct |
381 ms |
176072 KB |
Output is correct |
7 |
Correct |
402 ms |
175984 KB |
Output is correct |
8 |
Correct |
360 ms |
175680 KB |
Output is correct |
9 |
Correct |
359 ms |
175608 KB |
Output is correct |
10 |
Correct |
391 ms |
175676 KB |
Output is correct |
11 |
Correct |
427 ms |
175948 KB |
Output is correct |
12 |
Correct |
546 ms |
175968 KB |
Output is correct |
13 |
Correct |
400 ms |
175948 KB |
Output is correct |
14 |
Correct |
3 ms |
3796 KB |
Output is correct |
15 |
Correct |
365 ms |
176108 KB |
Output is correct |
16 |
Correct |
425 ms |
176392 KB |
Output is correct |
17 |
Correct |
400 ms |
175836 KB |
Output is correct |
18 |
Correct |
351 ms |
175884 KB |
Output is correct |
19 |
Correct |
419 ms |
175948 KB |
Output is correct |
20 |
Correct |
360 ms |
175684 KB |
Output is correct |
21 |
Correct |
388 ms |
175788 KB |
Output is correct |
22 |
Correct |
406 ms |
175852 KB |
Output is correct |
23 |
Correct |
416 ms |
175964 KB |
Output is correct |
24 |
Correct |
518 ms |
175988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3796 KB |
Output is correct |
2 |
Correct |
413 ms |
174720 KB |
Output is correct |
3 |
Correct |
396 ms |
174908 KB |
Output is correct |
4 |
Correct |
356 ms |
175812 KB |
Output is correct |
5 |
Correct |
385 ms |
175724 KB |
Output is correct |
6 |
Correct |
381 ms |
176072 KB |
Output is correct |
7 |
Correct |
402 ms |
175984 KB |
Output is correct |
8 |
Correct |
360 ms |
175680 KB |
Output is correct |
9 |
Correct |
359 ms |
175608 KB |
Output is correct |
10 |
Correct |
391 ms |
175676 KB |
Output is correct |
11 |
Correct |
427 ms |
175948 KB |
Output is correct |
12 |
Correct |
546 ms |
175968 KB |
Output is correct |
13 |
Correct |
400 ms |
175948 KB |
Output is correct |
14 |
Correct |
3 ms |
3796 KB |
Output is correct |
15 |
Correct |
365 ms |
176108 KB |
Output is correct |
16 |
Correct |
425 ms |
176392 KB |
Output is correct |
17 |
Correct |
400 ms |
175836 KB |
Output is correct |
18 |
Correct |
351 ms |
175884 KB |
Output is correct |
19 |
Correct |
419 ms |
175948 KB |
Output is correct |
20 |
Correct |
360 ms |
175684 KB |
Output is correct |
21 |
Correct |
388 ms |
175788 KB |
Output is correct |
22 |
Correct |
406 ms |
175852 KB |
Output is correct |
23 |
Correct |
416 ms |
175964 KB |
Output is correct |
24 |
Correct |
518 ms |
175988 KB |
Output is correct |
25 |
Correct |
353 ms |
175296 KB |
Output is correct |
26 |
Correct |
398 ms |
176352 KB |
Output is correct |
27 |
Correct |
362 ms |
175812 KB |
Output is correct |
28 |
Correct |
358 ms |
175812 KB |
Output is correct |
29 |
Correct |
395 ms |
176244 KB |
Output is correct |
30 |
Correct |
385 ms |
176008 KB |
Output is correct |
31 |
Correct |
399 ms |
175728 KB |
Output is correct |
32 |
Correct |
527 ms |
175944 KB |
Output is correct |
33 |
Correct |
781 ms |
175912 KB |
Output is correct |
34 |
Correct |
1062 ms |
175788 KB |
Output is correct |
35 |
Correct |
787 ms |
175932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3792 KB |
Output is correct |
2 |
Correct |
3204 ms |
1391124 KB |
Output is correct |
3 |
Correct |
3150 ms |
1389692 KB |
Output is correct |
4 |
Correct |
3016 ms |
1389940 KB |
Output is correct |
5 |
Correct |
3154 ms |
1389756 KB |
Output is correct |
6 |
Correct |
3235 ms |
1389924 KB |
Output is correct |
7 |
Correct |
2969 ms |
1389752 KB |
Output is correct |
8 |
Correct |
3 ms |
3796 KB |
Output is correct |
9 |
Correct |
413 ms |
174720 KB |
Output is correct |
10 |
Correct |
396 ms |
174908 KB |
Output is correct |
11 |
Correct |
356 ms |
175812 KB |
Output is correct |
12 |
Correct |
385 ms |
175724 KB |
Output is correct |
13 |
Correct |
381 ms |
176072 KB |
Output is correct |
14 |
Correct |
402 ms |
175984 KB |
Output is correct |
15 |
Correct |
360 ms |
175680 KB |
Output is correct |
16 |
Correct |
359 ms |
175608 KB |
Output is correct |
17 |
Correct |
391 ms |
175676 KB |
Output is correct |
18 |
Correct |
427 ms |
175948 KB |
Output is correct |
19 |
Correct |
546 ms |
175968 KB |
Output is correct |
20 |
Correct |
400 ms |
175948 KB |
Output is correct |
21 |
Correct |
3 ms |
3796 KB |
Output is correct |
22 |
Correct |
365 ms |
176108 KB |
Output is correct |
23 |
Correct |
425 ms |
176392 KB |
Output is correct |
24 |
Correct |
400 ms |
175836 KB |
Output is correct |
25 |
Correct |
351 ms |
175884 KB |
Output is correct |
26 |
Correct |
419 ms |
175948 KB |
Output is correct |
27 |
Correct |
360 ms |
175684 KB |
Output is correct |
28 |
Correct |
388 ms |
175788 KB |
Output is correct |
29 |
Correct |
406 ms |
175852 KB |
Output is correct |
30 |
Correct |
416 ms |
175964 KB |
Output is correct |
31 |
Correct |
518 ms |
175988 KB |
Output is correct |
32 |
Correct |
353 ms |
175296 KB |
Output is correct |
33 |
Correct |
398 ms |
176352 KB |
Output is correct |
34 |
Correct |
362 ms |
175812 KB |
Output is correct |
35 |
Correct |
358 ms |
175812 KB |
Output is correct |
36 |
Correct |
395 ms |
176244 KB |
Output is correct |
37 |
Correct |
385 ms |
176008 KB |
Output is correct |
38 |
Correct |
399 ms |
175728 KB |
Output is correct |
39 |
Correct |
527 ms |
175944 KB |
Output is correct |
40 |
Correct |
781 ms |
175912 KB |
Output is correct |
41 |
Correct |
1062 ms |
175788 KB |
Output is correct |
42 |
Correct |
787 ms |
175932 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
5 ms |
3828 KB |
Output is correct |
45 |
Correct |
4223 ms |
1401408 KB |
Output is correct |
46 |
Correct |
3328 ms |
1396792 KB |
Output is correct |
47 |
Correct |
3375 ms |
1397172 KB |
Output is correct |
48 |
Correct |
3117 ms |
1399344 KB |
Output is correct |
49 |
Correct |
4429 ms |
1401384 KB |
Output is correct |
50 |
Correct |
3503 ms |
1399060 KB |
Output is correct |
51 |
Correct |
3029 ms |
1399472 KB |
Output is correct |
52 |
Correct |
3294 ms |
1397116 KB |
Output is correct |
53 |
Correct |
6597 ms |
1397844 KB |
Output is correct |
54 |
Correct |
3897 ms |
1398884 KB |
Output is correct |
55 |
Correct |
4406 ms |
1397964 KB |
Output is correct |
56 |
Correct |
6174 ms |
1398580 KB |
Output is correct |
57 |
Correct |
5682 ms |
1398812 KB |
Output is correct |
58 |
Correct |
5800 ms |
1398732 KB |
Output is correct |
59 |
Correct |
5836 ms |
1398824 KB |
Output is correct |
60 |
Correct |
6500 ms |
1398152 KB |
Output is correct |
61 |
Correct |
5817 ms |
1398016 KB |
Output is correct |