#include "dungeons.h"
#include <bits/stdc++.h>
using ll = long long;
using std::vector;
struct dungeon {
int s, p, w, l;
};
struct info {
int pos, thres;
ll sum;
info() = default;
};
constexpr int LOG = 24;
int size;
vector<dungeon> data;
vector<info> lift[LOG][LOG];
vector<info> win_all[LOG];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
size = n;
data.reserve(n);
for (int i = 0; i < n; ++i) {
data.push_back({s[i], p[i], w[i], l[i]});
}
for (int stage = 0; stage < LOG; ++stage) {
lift[stage][0].resize(n + 1);
const int lb = 1 << stage;
const int ub = 1 << (stage + 1);
for (int i = 0; i < n; ++i) {
if (s[i] < lb) {
lift[stage][0][i] = {w[i], std::max(0, ub - s[i]), s[i]};
} else if (s[i] >= ub) {
lift[stage][0][i] = {l[i], std::max(0, ub - p[i]), p[i]};
} else {
lift[stage][0][i] = {l[i], std::max(0, std::min(s[i], ub - p[i])), p[i]};
}
}
lift[stage][0][n] = {n, 0, 0};
for (int k = 0; k < stage; ++k) {
lift[stage][k + 1].resize(n + 1);
for (int i = 0; i <= n; ++i) {
const auto [p0, t0, s0] = lift[stage][k][i];
const auto [p1, t1, s1] = lift[stage][k][p0];
lift[stage][k + 1][i] = {p1, s0 >= t1 ? 0 : std::min<int>(t0, t1 - s0), s0 + s1};
}
}
}
win_all[0].resize(n + 1);
for (int i = 0; i < n; ++i) {
win_all[0][i] = {w[i], 0, s[i]};
}
win_all[0][n] = {n, 0, 0};
for (int k = 0; k < LOG - 1; ++k) {
win_all[k + 1].resize(n + 1);
for (int i = 0; i <= n; ++i) {
const auto [p0, t0, s0] = win_all[k][i];
const auto [p1, t1, s1] = win_all[k][p0];
win_all[k + 1][i] = {p1, 0, s0 + s1};
}
}
}
ll simulate(int x, int z) {
int stage = 0;
while (true) {
while (z >= (1 << (stage + 1))) {
stage += 1;
}
if (x == size) {
return z;
}
if (stage >= LOG) {
break;
}
for (int k = stage; k >= 0; --k) {
if (lift[stage][k][x].pos != size and z < lift[stage][k][x].thres) {
z += lift[stage][k][x].sum;
x = lift[stage][k][x].pos;
}
}
if (z >= data[x].s) {
z += data[x].s;
x = data[x].w;
} else {
z += data[x].p;
x = data[x].l;
}
}
ll ret = z;
for (int k = LOG - 1; k >= 0; --k) {
if (win_all[k][x].pos != size) {
ret += win_all[k][x].sum;
x = win_all[k][x].pos;
}
}
ret += data[x].s;
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
8 ms |
10452 KB |
Output is correct |
4 |
Correct |
153 ms |
257192 KB |
Output is correct |
5 |
Correct |
8 ms |
10452 KB |
Output is correct |
6 |
Correct |
154 ms |
257160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5464 KB |
Output is correct |
2 |
Correct |
1920 ms |
2056320 KB |
Output is correct |
3 |
Correct |
1475 ms |
2056520 KB |
Output is correct |
4 |
Correct |
1615 ms |
2057948 KB |
Output is correct |
5 |
Correct |
1569 ms |
2057912 KB |
Output is correct |
6 |
Correct |
2533 ms |
2056392 KB |
Output is correct |
7 |
Correct |
2426 ms |
2054736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5460 KB |
Output is correct |
2 |
Correct |
272 ms |
259584 KB |
Output is correct |
3 |
Correct |
255 ms |
259708 KB |
Output is correct |
4 |
Correct |
243 ms |
259096 KB |
Output is correct |
5 |
Correct |
216 ms |
259080 KB |
Output is correct |
6 |
Correct |
542 ms |
259252 KB |
Output is correct |
7 |
Correct |
663 ms |
259232 KB |
Output is correct |
8 |
Correct |
580 ms |
259016 KB |
Output is correct |
9 |
Correct |
216 ms |
259060 KB |
Output is correct |
10 |
Correct |
508 ms |
258764 KB |
Output is correct |
11 |
Correct |
704 ms |
259184 KB |
Output is correct |
12 |
Correct |
1763 ms |
259436 KB |
Output is correct |
13 |
Correct |
1784 ms |
259144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5460 KB |
Output is correct |
2 |
Correct |
272 ms |
259584 KB |
Output is correct |
3 |
Correct |
255 ms |
259708 KB |
Output is correct |
4 |
Correct |
243 ms |
259096 KB |
Output is correct |
5 |
Correct |
216 ms |
259080 KB |
Output is correct |
6 |
Correct |
542 ms |
259252 KB |
Output is correct |
7 |
Correct |
663 ms |
259232 KB |
Output is correct |
8 |
Correct |
580 ms |
259016 KB |
Output is correct |
9 |
Correct |
216 ms |
259060 KB |
Output is correct |
10 |
Correct |
508 ms |
258764 KB |
Output is correct |
11 |
Correct |
704 ms |
259184 KB |
Output is correct |
12 |
Correct |
1763 ms |
259436 KB |
Output is correct |
13 |
Correct |
1784 ms |
259144 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
219 ms |
259356 KB |
Output is correct |
16 |
Correct |
249 ms |
259640 KB |
Output is correct |
17 |
Correct |
343 ms |
259144 KB |
Output is correct |
18 |
Correct |
335 ms |
259116 KB |
Output is correct |
19 |
Correct |
491 ms |
259216 KB |
Output is correct |
20 |
Correct |
440 ms |
258912 KB |
Output is correct |
21 |
Correct |
571 ms |
259148 KB |
Output is correct |
22 |
Correct |
514 ms |
259024 KB |
Output is correct |
23 |
Correct |
861 ms |
259280 KB |
Output is correct |
24 |
Correct |
1028 ms |
259172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5460 KB |
Output is correct |
2 |
Correct |
272 ms |
259584 KB |
Output is correct |
3 |
Correct |
255 ms |
259708 KB |
Output is correct |
4 |
Correct |
243 ms |
259096 KB |
Output is correct |
5 |
Correct |
216 ms |
259080 KB |
Output is correct |
6 |
Correct |
542 ms |
259252 KB |
Output is correct |
7 |
Correct |
663 ms |
259232 KB |
Output is correct |
8 |
Correct |
580 ms |
259016 KB |
Output is correct |
9 |
Correct |
216 ms |
259060 KB |
Output is correct |
10 |
Correct |
508 ms |
258764 KB |
Output is correct |
11 |
Correct |
704 ms |
259184 KB |
Output is correct |
12 |
Correct |
1763 ms |
259436 KB |
Output is correct |
13 |
Correct |
1784 ms |
259144 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
219 ms |
259356 KB |
Output is correct |
16 |
Correct |
249 ms |
259640 KB |
Output is correct |
17 |
Correct |
343 ms |
259144 KB |
Output is correct |
18 |
Correct |
335 ms |
259116 KB |
Output is correct |
19 |
Correct |
491 ms |
259216 KB |
Output is correct |
20 |
Correct |
440 ms |
258912 KB |
Output is correct |
21 |
Correct |
571 ms |
259148 KB |
Output is correct |
22 |
Correct |
514 ms |
259024 KB |
Output is correct |
23 |
Correct |
861 ms |
259280 KB |
Output is correct |
24 |
Correct |
1028 ms |
259172 KB |
Output is correct |
25 |
Correct |
175 ms |
258472 KB |
Output is correct |
26 |
Correct |
246 ms |
259524 KB |
Output is correct |
27 |
Correct |
220 ms |
259036 KB |
Output is correct |
28 |
Correct |
219 ms |
259080 KB |
Output is correct |
29 |
Correct |
324 ms |
259468 KB |
Output is correct |
30 |
Correct |
454 ms |
259212 KB |
Output is correct |
31 |
Correct |
593 ms |
258872 KB |
Output is correct |
32 |
Correct |
734 ms |
259052 KB |
Output is correct |
33 |
Correct |
698 ms |
259152 KB |
Output is correct |
34 |
Correct |
1221 ms |
258980 KB |
Output is correct |
35 |
Correct |
713 ms |
259104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5464 KB |
Output is correct |
2 |
Correct |
1920 ms |
2056320 KB |
Output is correct |
3 |
Correct |
1475 ms |
2056520 KB |
Output is correct |
4 |
Correct |
1615 ms |
2057948 KB |
Output is correct |
5 |
Correct |
1569 ms |
2057912 KB |
Output is correct |
6 |
Correct |
2533 ms |
2056392 KB |
Output is correct |
7 |
Correct |
2426 ms |
2054736 KB |
Output is correct |
8 |
Correct |
6 ms |
5460 KB |
Output is correct |
9 |
Correct |
272 ms |
259584 KB |
Output is correct |
10 |
Correct |
255 ms |
259708 KB |
Output is correct |
11 |
Correct |
243 ms |
259096 KB |
Output is correct |
12 |
Correct |
216 ms |
259080 KB |
Output is correct |
13 |
Correct |
542 ms |
259252 KB |
Output is correct |
14 |
Correct |
663 ms |
259232 KB |
Output is correct |
15 |
Correct |
580 ms |
259016 KB |
Output is correct |
16 |
Correct |
216 ms |
259060 KB |
Output is correct |
17 |
Correct |
508 ms |
258764 KB |
Output is correct |
18 |
Correct |
704 ms |
259184 KB |
Output is correct |
19 |
Correct |
1763 ms |
259436 KB |
Output is correct |
20 |
Correct |
1784 ms |
259144 KB |
Output is correct |
21 |
Correct |
4 ms |
5460 KB |
Output is correct |
22 |
Correct |
219 ms |
259356 KB |
Output is correct |
23 |
Correct |
249 ms |
259640 KB |
Output is correct |
24 |
Correct |
343 ms |
259144 KB |
Output is correct |
25 |
Correct |
335 ms |
259116 KB |
Output is correct |
26 |
Correct |
491 ms |
259216 KB |
Output is correct |
27 |
Correct |
440 ms |
258912 KB |
Output is correct |
28 |
Correct |
571 ms |
259148 KB |
Output is correct |
29 |
Correct |
514 ms |
259024 KB |
Output is correct |
30 |
Correct |
861 ms |
259280 KB |
Output is correct |
31 |
Correct |
1028 ms |
259172 KB |
Output is correct |
32 |
Correct |
175 ms |
258472 KB |
Output is correct |
33 |
Correct |
246 ms |
259524 KB |
Output is correct |
34 |
Correct |
220 ms |
259036 KB |
Output is correct |
35 |
Correct |
219 ms |
259080 KB |
Output is correct |
36 |
Correct |
324 ms |
259468 KB |
Output is correct |
37 |
Correct |
454 ms |
259212 KB |
Output is correct |
38 |
Correct |
593 ms |
258872 KB |
Output is correct |
39 |
Correct |
734 ms |
259052 KB |
Output is correct |
40 |
Correct |
698 ms |
259152 KB |
Output is correct |
41 |
Correct |
1221 ms |
258980 KB |
Output is correct |
42 |
Correct |
713 ms |
259104 KB |
Output is correct |
43 |
Correct |
0 ms |
312 KB |
Output is correct |
44 |
Correct |
6 ms |
5460 KB |
Output is correct |
45 |
Correct |
1806 ms |
2061088 KB |
Output is correct |
46 |
Correct |
1584 ms |
2056432 KB |
Output is correct |
47 |
Correct |
1641 ms |
2056836 KB |
Output is correct |
48 |
Correct |
1521 ms |
2059172 KB |
Output is correct |
49 |
Correct |
1699 ms |
2061128 KB |
Output is correct |
50 |
Correct |
1880 ms |
2058644 KB |
Output is correct |
51 |
Correct |
1479 ms |
2059088 KB |
Output is correct |
52 |
Correct |
2075 ms |
2056772 KB |
Output is correct |
53 |
Correct |
2858 ms |
2057684 KB |
Output is correct |
54 |
Correct |
2431 ms |
2058784 KB |
Output is correct |
55 |
Correct |
2756 ms |
2057720 KB |
Output is correct |
56 |
Correct |
2720 ms |
2058400 KB |
Output is correct |
57 |
Correct |
2831 ms |
2058448 KB |
Output is correct |
58 |
Correct |
2690 ms |
2058604 KB |
Output is correct |
59 |
Correct |
2732 ms |
2058592 KB |
Output is correct |
60 |
Correct |
2552 ms |
2058052 KB |
Output is correct |
61 |
Correct |
2363 ms |
2057772 KB |
Output is correct |