#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define mk make_pair
typedef pair <ll, ll> pii;
const int N = 400023, LG = 24, L2 = 9, K = 5;
int s[N], p[N], o[N], l[N], n;
long long m[N], a[N];
pair <int, pii> nx[LG][N][L2];
const ll INF = 1e18;
void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
n = nn;
for (int i = 0; i < n; i++) {
s[i] = ss[i];
p[i] = pp[i];
o[i] = ww[i];
l[i] = ll[i];
}
m[n] = 0;
a[n] = 0;
l[n] = n;
o[n] = n;
s[n] = 0;
for (int i = n - 1; i >= 0; i--) {
a[i] = a[o[i]] + s[i];
m[i] = max((long long)s[i], m[o[i]] - s[i]);
}
for (int w = 0; w < LG; w++) {
for (int i = 0; i <= n; i++) {
if (i < n && s[i] <= (1 << w)) {
nx[w][i][0].F = o[i];
nx[w][i][0].S.F = INF;
nx[w][i][0].S.S = s[i];
} else {
nx[w][i][0].F = l[i];
nx[w][i][0].S.F = s[i] - 1;
nx[w][i][0].S.S = p[i];
}
}
for (int j = 1; j < L2; j++) {
for (int i = 0; i <= n; i++) {
nx[w][i][j].S.S = nx[w][i][j - 1].S.S;
nx[w][i][j].S.F = nx[w][i][j - 1].S.F;
nx[w][i][j].F = nx[w][i][j - 1].F;
for (int k = 0; k < K; k++) {
int y = nx[w][i][j].F;
nx[w][i][j].F = nx[w][y][j - 1].F;
nx[w][i][j].S.F = min (nx[w][i][j].S.F, nx[w][y][j - 1].S.F - nx[w][i][j].S.S);
nx[w][i][j].S.S = nx[w][i][j].S.S + nx[w][y][j - 1].S.S;
}
}
}
}
return;
}
pair <int, long long> findd (int w, int x, ll z) {
for (int i = L2 - 1; i >= 0; i--) {
for (int k = 0; k < K; k++) {
if (z <= nx[w][x][i].S.F) {
z += nx[w][x][i].S.S;
x = nx[w][x][i].F;
}
}
}
return {x, z};
}
ll ans (int x, ll z) {
if (z >= m[x])
return z + a[x];
int l = 0;
while ((1 << l) < s[x])
l++;
pair <int, ll> pp = findd (l, x, z);
x = pp.F;
z = pp.S;
return ans (x, z);
}
long long simulate(int x, int z) {
pair <int, ll> pp = findd (0, x, z);
x = pp.F;
z = pp.S;
ll w = ans (x, z);
return w;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
57692 KB |
Output is correct |
2 |
Correct |
4 ms |
57692 KB |
Output is correct |
3 |
Correct |
9 ms |
68360 KB |
Output is correct |
4 |
Correct |
199 ms |
288692 KB |
Output is correct |
5 |
Correct |
10 ms |
68444 KB |
Output is correct |
6 |
Correct |
197 ms |
288808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
68188 KB |
Output is correct |
2 |
Correct |
3458 ms |
2059992 KB |
Output is correct |
3 |
Correct |
3124 ms |
2061900 KB |
Output is correct |
4 |
Correct |
2943 ms |
2063004 KB |
Output is correct |
5 |
Correct |
2429 ms |
2063120 KB |
Output is correct |
6 |
Correct |
3631 ms |
2061740 KB |
Output is correct |
7 |
Correct |
3231 ms |
2060368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
68188 KB |
Output is correct |
2 |
Correct |
245 ms |
290008 KB |
Output is correct |
3 |
Correct |
202 ms |
290232 KB |
Output is correct |
4 |
Correct |
201 ms |
289620 KB |
Output is correct |
5 |
Correct |
193 ms |
289600 KB |
Output is correct |
6 |
Correct |
240 ms |
289856 KB |
Output is correct |
7 |
Correct |
242 ms |
289676 KB |
Output is correct |
8 |
Correct |
192 ms |
289360 KB |
Output is correct |
9 |
Correct |
198 ms |
289392 KB |
Output is correct |
10 |
Correct |
201 ms |
289240 KB |
Output is correct |
11 |
Correct |
372 ms |
289692 KB |
Output is correct |
12 |
Correct |
469 ms |
289856 KB |
Output is correct |
13 |
Correct |
249 ms |
289620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
68188 KB |
Output is correct |
2 |
Correct |
245 ms |
290008 KB |
Output is correct |
3 |
Correct |
202 ms |
290232 KB |
Output is correct |
4 |
Correct |
201 ms |
289620 KB |
Output is correct |
5 |
Correct |
193 ms |
289600 KB |
Output is correct |
6 |
Correct |
240 ms |
289856 KB |
Output is correct |
7 |
Correct |
242 ms |
289676 KB |
Output is correct |
8 |
Correct |
192 ms |
289360 KB |
Output is correct |
9 |
Correct |
198 ms |
289392 KB |
Output is correct |
10 |
Correct |
201 ms |
289240 KB |
Output is correct |
11 |
Correct |
372 ms |
289692 KB |
Output is correct |
12 |
Correct |
469 ms |
289856 KB |
Output is correct |
13 |
Correct |
249 ms |
289620 KB |
Output is correct |
14 |
Correct |
7 ms |
68184 KB |
Output is correct |
15 |
Correct |
220 ms |
288576 KB |
Output is correct |
16 |
Correct |
262 ms |
289872 KB |
Output is correct |
17 |
Correct |
210 ms |
289604 KB |
Output is correct |
18 |
Correct |
229 ms |
289616 KB |
Output is correct |
19 |
Correct |
241 ms |
289616 KB |
Output is correct |
20 |
Correct |
235 ms |
289616 KB |
Output is correct |
21 |
Correct |
211 ms |
289620 KB |
Output is correct |
22 |
Correct |
219 ms |
289620 KB |
Output is correct |
23 |
Correct |
349 ms |
289620 KB |
Output is correct |
24 |
Correct |
422 ms |
289680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
68188 KB |
Output is correct |
2 |
Correct |
245 ms |
290008 KB |
Output is correct |
3 |
Correct |
202 ms |
290232 KB |
Output is correct |
4 |
Correct |
201 ms |
289620 KB |
Output is correct |
5 |
Correct |
193 ms |
289600 KB |
Output is correct |
6 |
Correct |
240 ms |
289856 KB |
Output is correct |
7 |
Correct |
242 ms |
289676 KB |
Output is correct |
8 |
Correct |
192 ms |
289360 KB |
Output is correct |
9 |
Correct |
198 ms |
289392 KB |
Output is correct |
10 |
Correct |
201 ms |
289240 KB |
Output is correct |
11 |
Correct |
372 ms |
289692 KB |
Output is correct |
12 |
Correct |
469 ms |
289856 KB |
Output is correct |
13 |
Correct |
249 ms |
289620 KB |
Output is correct |
14 |
Correct |
7 ms |
68184 KB |
Output is correct |
15 |
Correct |
220 ms |
288576 KB |
Output is correct |
16 |
Correct |
262 ms |
289872 KB |
Output is correct |
17 |
Correct |
210 ms |
289604 KB |
Output is correct |
18 |
Correct |
229 ms |
289616 KB |
Output is correct |
19 |
Correct |
241 ms |
289616 KB |
Output is correct |
20 |
Correct |
235 ms |
289616 KB |
Output is correct |
21 |
Correct |
211 ms |
289620 KB |
Output is correct |
22 |
Correct |
219 ms |
289620 KB |
Output is correct |
23 |
Correct |
349 ms |
289620 KB |
Output is correct |
24 |
Correct |
422 ms |
289680 KB |
Output is correct |
25 |
Correct |
231 ms |
289104 KB |
Output is correct |
26 |
Correct |
240 ms |
289960 KB |
Output is correct |
27 |
Correct |
220 ms |
289664 KB |
Output is correct |
28 |
Correct |
222 ms |
289600 KB |
Output is correct |
29 |
Correct |
250 ms |
287824 KB |
Output is correct |
30 |
Correct |
270 ms |
289752 KB |
Output is correct |
31 |
Correct |
287 ms |
289360 KB |
Output is correct |
32 |
Correct |
433 ms |
289620 KB |
Output is correct |
33 |
Correct |
281 ms |
289616 KB |
Output is correct |
34 |
Correct |
551 ms |
289616 KB |
Output is correct |
35 |
Correct |
319 ms |
287572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
68188 KB |
Output is correct |
2 |
Correct |
3458 ms |
2059992 KB |
Output is correct |
3 |
Correct |
3124 ms |
2061900 KB |
Output is correct |
4 |
Correct |
2943 ms |
2063004 KB |
Output is correct |
5 |
Correct |
2429 ms |
2063120 KB |
Output is correct |
6 |
Correct |
3631 ms |
2061740 KB |
Output is correct |
7 |
Correct |
3231 ms |
2060368 KB |
Output is correct |
8 |
Correct |
8 ms |
68188 KB |
Output is correct |
9 |
Correct |
245 ms |
290008 KB |
Output is correct |
10 |
Correct |
202 ms |
290232 KB |
Output is correct |
11 |
Correct |
201 ms |
289620 KB |
Output is correct |
12 |
Correct |
193 ms |
289600 KB |
Output is correct |
13 |
Correct |
240 ms |
289856 KB |
Output is correct |
14 |
Correct |
242 ms |
289676 KB |
Output is correct |
15 |
Correct |
192 ms |
289360 KB |
Output is correct |
16 |
Correct |
198 ms |
289392 KB |
Output is correct |
17 |
Correct |
201 ms |
289240 KB |
Output is correct |
18 |
Correct |
372 ms |
289692 KB |
Output is correct |
19 |
Correct |
469 ms |
289856 KB |
Output is correct |
20 |
Correct |
249 ms |
289620 KB |
Output is correct |
21 |
Correct |
7 ms |
68184 KB |
Output is correct |
22 |
Correct |
220 ms |
288576 KB |
Output is correct |
23 |
Correct |
262 ms |
289872 KB |
Output is correct |
24 |
Correct |
210 ms |
289604 KB |
Output is correct |
25 |
Correct |
229 ms |
289616 KB |
Output is correct |
26 |
Correct |
241 ms |
289616 KB |
Output is correct |
27 |
Correct |
235 ms |
289616 KB |
Output is correct |
28 |
Correct |
211 ms |
289620 KB |
Output is correct |
29 |
Correct |
219 ms |
289620 KB |
Output is correct |
30 |
Correct |
349 ms |
289620 KB |
Output is correct |
31 |
Correct |
422 ms |
289680 KB |
Output is correct |
32 |
Correct |
231 ms |
289104 KB |
Output is correct |
33 |
Correct |
240 ms |
289960 KB |
Output is correct |
34 |
Correct |
220 ms |
289664 KB |
Output is correct |
35 |
Correct |
222 ms |
289600 KB |
Output is correct |
36 |
Correct |
250 ms |
287824 KB |
Output is correct |
37 |
Correct |
270 ms |
289752 KB |
Output is correct |
38 |
Correct |
287 ms |
289360 KB |
Output is correct |
39 |
Correct |
433 ms |
289620 KB |
Output is correct |
40 |
Correct |
281 ms |
289616 KB |
Output is correct |
41 |
Correct |
551 ms |
289616 KB |
Output is correct |
42 |
Correct |
319 ms |
287572 KB |
Output is correct |
43 |
Correct |
4 ms |
57692 KB |
Output is correct |
44 |
Correct |
7 ms |
68188 KB |
Output is correct |
45 |
Correct |
3608 ms |
2064992 KB |
Output is correct |
46 |
Correct |
2650 ms |
2061344 KB |
Output is correct |
47 |
Correct |
2814 ms |
2061704 KB |
Output is correct |
48 |
Correct |
2392 ms |
2063160 KB |
Output is correct |
49 |
Correct |
3842 ms |
2064972 KB |
Output is correct |
50 |
Correct |
3396 ms |
2061564 KB |
Output is correct |
51 |
Correct |
2269 ms |
2059680 KB |
Output is correct |
52 |
Correct |
3520 ms |
2055248 KB |
Output is correct |
53 |
Execution timed out |
7119 ms |
1211204 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |