#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
#define F first
#define S second
#define mk make_pair
typedef pair <int, int> pii;
const int N = 400023, LG = 24, L2 = 11, K = 4;
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 = 1e8;
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;
int wef = nx[w][y][j - 1].S.F - nx[w][i][j].S.S;
if (wef < 0)
wef = -1;
nx[w][i][j].S.F = min (nx[w][i][j].S.F, wef);
nx[w][i][j].S.S = min ({(int)1e9, 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) {
if (z <= nx[w][x][L2 - 1].S.F) {
z += nx[w][x][L2 - 1].S.S;
x = nx[w][x][L2 - 1].F;
}
for (int i = L2 - 2; 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 |
57832 KB |
Output is correct |
3 |
Correct |
8 ms |
66140 KB |
Output is correct |
4 |
Correct |
138 ms |
191316 KB |
Output is correct |
5 |
Correct |
8 ms |
66144 KB |
Output is correct |
6 |
Correct |
146 ms |
186136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
62216 KB |
Output is correct |
2 |
Correct |
1704 ms |
1266460 KB |
Output is correct |
3 |
Correct |
1545 ms |
1266060 KB |
Output is correct |
4 |
Correct |
1544 ms |
1266080 KB |
Output is correct |
5 |
Correct |
1854 ms |
1266200 KB |
Output is correct |
6 |
Correct |
1669 ms |
1266020 KB |
Output is correct |
7 |
Correct |
1551 ms |
1266148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
62040 KB |
Output is correct |
2 |
Correct |
184 ms |
191208 KB |
Output is correct |
3 |
Correct |
207 ms |
191420 KB |
Output is correct |
4 |
Correct |
141 ms |
193248 KB |
Output is correct |
5 |
Correct |
156 ms |
193504 KB |
Output is correct |
6 |
Correct |
202 ms |
193528 KB |
Output is correct |
7 |
Correct |
224 ms |
193332 KB |
Output is correct |
8 |
Correct |
137 ms |
194384 KB |
Output is correct |
9 |
Correct |
158 ms |
192336 KB |
Output is correct |
10 |
Correct |
135 ms |
192052 KB |
Output is correct |
11 |
Correct |
239 ms |
194564 KB |
Output is correct |
12 |
Correct |
337 ms |
194256 KB |
Output is correct |
13 |
Correct |
190 ms |
194644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
62040 KB |
Output is correct |
2 |
Correct |
184 ms |
191208 KB |
Output is correct |
3 |
Correct |
207 ms |
191420 KB |
Output is correct |
4 |
Correct |
141 ms |
193248 KB |
Output is correct |
5 |
Correct |
156 ms |
193504 KB |
Output is correct |
6 |
Correct |
202 ms |
193528 KB |
Output is correct |
7 |
Correct |
224 ms |
193332 KB |
Output is correct |
8 |
Correct |
137 ms |
194384 KB |
Output is correct |
9 |
Correct |
158 ms |
192336 KB |
Output is correct |
10 |
Correct |
135 ms |
192052 KB |
Output is correct |
11 |
Correct |
239 ms |
194564 KB |
Output is correct |
12 |
Correct |
337 ms |
194256 KB |
Output is correct |
13 |
Correct |
190 ms |
194644 KB |
Output is correct |
14 |
Correct |
8 ms |
62044 KB |
Output is correct |
15 |
Correct |
173 ms |
194628 KB |
Output is correct |
16 |
Correct |
177 ms |
194988 KB |
Output is correct |
17 |
Correct |
162 ms |
194388 KB |
Output is correct |
18 |
Correct |
154 ms |
192580 KB |
Output is correct |
19 |
Correct |
161 ms |
192596 KB |
Output is correct |
20 |
Correct |
167 ms |
192188 KB |
Output is correct |
21 |
Correct |
138 ms |
192316 KB |
Output is correct |
22 |
Correct |
179 ms |
192328 KB |
Output is correct |
23 |
Correct |
237 ms |
192460 KB |
Output is correct |
24 |
Correct |
298 ms |
192704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
62040 KB |
Output is correct |
2 |
Correct |
184 ms |
191208 KB |
Output is correct |
3 |
Correct |
207 ms |
191420 KB |
Output is correct |
4 |
Correct |
141 ms |
193248 KB |
Output is correct |
5 |
Correct |
156 ms |
193504 KB |
Output is correct |
6 |
Correct |
202 ms |
193528 KB |
Output is correct |
7 |
Correct |
224 ms |
193332 KB |
Output is correct |
8 |
Correct |
137 ms |
194384 KB |
Output is correct |
9 |
Correct |
158 ms |
192336 KB |
Output is correct |
10 |
Correct |
135 ms |
192052 KB |
Output is correct |
11 |
Correct |
239 ms |
194564 KB |
Output is correct |
12 |
Correct |
337 ms |
194256 KB |
Output is correct |
13 |
Correct |
190 ms |
194644 KB |
Output is correct |
14 |
Correct |
8 ms |
62044 KB |
Output is correct |
15 |
Correct |
173 ms |
194628 KB |
Output is correct |
16 |
Correct |
177 ms |
194988 KB |
Output is correct |
17 |
Correct |
162 ms |
194388 KB |
Output is correct |
18 |
Correct |
154 ms |
192580 KB |
Output is correct |
19 |
Correct |
161 ms |
192596 KB |
Output is correct |
20 |
Correct |
167 ms |
192188 KB |
Output is correct |
21 |
Correct |
138 ms |
192316 KB |
Output is correct |
22 |
Correct |
179 ms |
192328 KB |
Output is correct |
23 |
Correct |
237 ms |
192460 KB |
Output is correct |
24 |
Correct |
298 ms |
192704 KB |
Output is correct |
25 |
Correct |
158 ms |
193856 KB |
Output is correct |
26 |
Correct |
183 ms |
192944 KB |
Output is correct |
27 |
Correct |
144 ms |
192344 KB |
Output is correct |
28 |
Correct |
174 ms |
192428 KB |
Output is correct |
29 |
Correct |
202 ms |
192840 KB |
Output is correct |
30 |
Correct |
170 ms |
192592 KB |
Output is correct |
31 |
Correct |
196 ms |
192328 KB |
Output is correct |
32 |
Correct |
313 ms |
192320 KB |
Output is correct |
33 |
Correct |
228 ms |
192404 KB |
Output is correct |
34 |
Correct |
437 ms |
192372 KB |
Output is correct |
35 |
Correct |
210 ms |
192544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
62216 KB |
Output is correct |
2 |
Correct |
1704 ms |
1266460 KB |
Output is correct |
3 |
Correct |
1545 ms |
1266060 KB |
Output is correct |
4 |
Correct |
1544 ms |
1266080 KB |
Output is correct |
5 |
Correct |
1854 ms |
1266200 KB |
Output is correct |
6 |
Correct |
1669 ms |
1266020 KB |
Output is correct |
7 |
Correct |
1551 ms |
1266148 KB |
Output is correct |
8 |
Correct |
7 ms |
62040 KB |
Output is correct |
9 |
Correct |
184 ms |
191208 KB |
Output is correct |
10 |
Correct |
207 ms |
191420 KB |
Output is correct |
11 |
Correct |
141 ms |
193248 KB |
Output is correct |
12 |
Correct |
156 ms |
193504 KB |
Output is correct |
13 |
Correct |
202 ms |
193528 KB |
Output is correct |
14 |
Correct |
224 ms |
193332 KB |
Output is correct |
15 |
Correct |
137 ms |
194384 KB |
Output is correct |
16 |
Correct |
158 ms |
192336 KB |
Output is correct |
17 |
Correct |
135 ms |
192052 KB |
Output is correct |
18 |
Correct |
239 ms |
194564 KB |
Output is correct |
19 |
Correct |
337 ms |
194256 KB |
Output is correct |
20 |
Correct |
190 ms |
194644 KB |
Output is correct |
21 |
Correct |
8 ms |
62044 KB |
Output is correct |
22 |
Correct |
173 ms |
194628 KB |
Output is correct |
23 |
Correct |
177 ms |
194988 KB |
Output is correct |
24 |
Correct |
162 ms |
194388 KB |
Output is correct |
25 |
Correct |
154 ms |
192580 KB |
Output is correct |
26 |
Correct |
161 ms |
192596 KB |
Output is correct |
27 |
Correct |
167 ms |
192188 KB |
Output is correct |
28 |
Correct |
138 ms |
192316 KB |
Output is correct |
29 |
Correct |
179 ms |
192328 KB |
Output is correct |
30 |
Correct |
237 ms |
192460 KB |
Output is correct |
31 |
Correct |
298 ms |
192704 KB |
Output is correct |
32 |
Correct |
158 ms |
193856 KB |
Output is correct |
33 |
Correct |
183 ms |
192944 KB |
Output is correct |
34 |
Correct |
144 ms |
192344 KB |
Output is correct |
35 |
Correct |
174 ms |
192428 KB |
Output is correct |
36 |
Correct |
202 ms |
192840 KB |
Output is correct |
37 |
Correct |
170 ms |
192592 KB |
Output is correct |
38 |
Correct |
196 ms |
192328 KB |
Output is correct |
39 |
Correct |
313 ms |
192320 KB |
Output is correct |
40 |
Correct |
228 ms |
192404 KB |
Output is correct |
41 |
Correct |
437 ms |
192372 KB |
Output is correct |
42 |
Correct |
210 ms |
192544 KB |
Output is correct |
43 |
Correct |
4 ms |
57688 KB |
Output is correct |
44 |
Correct |
6 ms |
62160 KB |
Output is correct |
45 |
Correct |
2477 ms |
1277208 KB |
Output is correct |
46 |
Correct |
1686 ms |
1272628 KB |
Output is correct |
47 |
Correct |
1652 ms |
1273240 KB |
Output is correct |
48 |
Correct |
1544 ms |
1275124 KB |
Output is correct |
49 |
Correct |
2349 ms |
1275664 KB |
Output is correct |
50 |
Correct |
1540 ms |
1270840 KB |
Output is correct |
51 |
Correct |
1498 ms |
1267412 KB |
Output is correct |
52 |
Correct |
1527 ms |
1267200 KB |
Output is correct |
53 |
Execution timed out |
7091 ms |
1267716 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |