#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
long long N;
const int mxt = 7;
long long f(int x)
{
long long r = 1;
long long w = 1;
while (x--)
{
w *= 8;
r *= w;
}
return r;
}
const int mxp = 18;
int mn1[mxt][400002][mxp];
int mx1[mxt][400002][mxp];
int tp[mxt][400002][mxp];
int del[mxt][400002][mxp];
long long mn[400002];
long long delt[400002];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = n;
mn[n] = -1e17;
delt[n] = 0;
for (int i = n - 1; i >= 0; i--)
{
mn[i] = max((long long)s[i], mn[w[i]] - s[i]);
delt[i] = s[i] + delt[w[i]];
}
for (int x = 0; x < mxt; x++)
{
long long v = f(x);
mn1[x][n][0] = -3e7;
mx1[x][n][0] = 3e7;
tp[x][n][0] = n;
del[x][n][0] = 0;
for (int i = 0; i < n; i++)
{
if (s[i] > v)
{
mn1[x][i][0] = -1e8;
mx1[x][i][0] = s[i] - 1;
tp[x][i][0] = l[i];
del[x][i][0] = p[i];
}
else
{
mn1[x][i][0] = s[i];
mx1[x][i][0] = 1e8;
tp[x][i][0] = w[i];
del[x][i][0] = s[i];
}
}
for (int t = 1; t < mxp; t++)
{
for (int i = 0; i <= n; i++)
{
int i_ = tp[x][i][t - 1];
int del_ = del[x][i][t - 1];
mn1[x][i][t] = max(mn1[x][i][t - 1], mn1[x][i_][t - 1] - del_);
mx1[x][i][t] = min(mx1[x][i][t - 1], mx1[x][i_][t - 1] - del_);
tp[x][i][t] = tp[x][i_][t - 1];
del[x][i][t] = del[x][i][t - 1] + del[x][i_][t - 1];
if (del[x][i][t] >= 2e8)
{
mn1[x][i][t] = mn1[x][i][t - 1];
mx1[x][i][t] = mx1[x][i][t - 1];
tp[x][i][t] = tp[x][i][t - 1];
del[x][i][t] = del[x][i][t - 1];
}
}
}
}
}
long long simulate(int x, int z) {
long long s = z;
while (s < mn[x])
{
for (int v = mxt - 1; v >= 0; v--)
{
if (s >= mn1[v][x][0] && s <= mx1[v][x][0])
for (int t = mxp - 1; t >= 0; t--)
{
if (s >= mn1[v][x][t] && s <= mx1[v][x][t])
{
s += del[v][x][t];
x = tp[v][x][t];
}
}
}
}
return s + delt[x];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
5 ms |
4508 KB |
Output is correct |
4 |
Correct |
242 ms |
101572 KB |
Output is correct |
5 |
Correct |
5 ms |
4556 KB |
Output is correct |
6 |
Correct |
265 ms |
101512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2508 KB |
Output is correct |
2 |
Correct |
2041 ms |
808900 KB |
Output is correct |
3 |
Correct |
1961 ms |
809684 KB |
Output is correct |
4 |
Correct |
1990 ms |
809996 KB |
Output is correct |
5 |
Correct |
2057 ms |
809924 KB |
Output is correct |
6 |
Correct |
2024 ms |
809664 KB |
Output is correct |
7 |
Correct |
1893 ms |
809784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2508 KB |
Output is correct |
2 |
Correct |
330 ms |
102228 KB |
Output is correct |
3 |
Correct |
270 ms |
102308 KB |
Output is correct |
4 |
Correct |
231 ms |
102260 KB |
Output is correct |
5 |
Correct |
249 ms |
102176 KB |
Output is correct |
6 |
Correct |
318 ms |
102344 KB |
Output is correct |
7 |
Correct |
592 ms |
102360 KB |
Output is correct |
8 |
Correct |
241 ms |
102264 KB |
Output is correct |
9 |
Correct |
250 ms |
102224 KB |
Output is correct |
10 |
Correct |
244 ms |
102176 KB |
Output is correct |
11 |
Correct |
439 ms |
102260 KB |
Output is correct |
12 |
Correct |
6530 ms |
102296 KB |
Output is correct |
13 |
Correct |
6071 ms |
102204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2508 KB |
Output is correct |
2 |
Correct |
330 ms |
102228 KB |
Output is correct |
3 |
Correct |
270 ms |
102308 KB |
Output is correct |
4 |
Correct |
231 ms |
102260 KB |
Output is correct |
5 |
Correct |
249 ms |
102176 KB |
Output is correct |
6 |
Correct |
318 ms |
102344 KB |
Output is correct |
7 |
Correct |
592 ms |
102360 KB |
Output is correct |
8 |
Correct |
241 ms |
102264 KB |
Output is correct |
9 |
Correct |
250 ms |
102224 KB |
Output is correct |
10 |
Correct |
244 ms |
102176 KB |
Output is correct |
11 |
Correct |
439 ms |
102260 KB |
Output is correct |
12 |
Correct |
6530 ms |
102296 KB |
Output is correct |
13 |
Correct |
6071 ms |
102204 KB |
Output is correct |
14 |
Correct |
3 ms |
2508 KB |
Output is correct |
15 |
Correct |
324 ms |
102356 KB |
Output is correct |
16 |
Correct |
364 ms |
102364 KB |
Output is correct |
17 |
Correct |
258 ms |
102272 KB |
Output is correct |
18 |
Correct |
250 ms |
102284 KB |
Output is correct |
19 |
Correct |
302 ms |
102316 KB |
Output is correct |
20 |
Correct |
268 ms |
102340 KB |
Output is correct |
21 |
Correct |
267 ms |
102176 KB |
Output is correct |
22 |
Correct |
350 ms |
102260 KB |
Output is correct |
23 |
Correct |
440 ms |
102296 KB |
Output is correct |
24 |
Correct |
850 ms |
102248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2508 KB |
Output is correct |
2 |
Correct |
330 ms |
102228 KB |
Output is correct |
3 |
Correct |
270 ms |
102308 KB |
Output is correct |
4 |
Correct |
231 ms |
102260 KB |
Output is correct |
5 |
Correct |
249 ms |
102176 KB |
Output is correct |
6 |
Correct |
318 ms |
102344 KB |
Output is correct |
7 |
Correct |
592 ms |
102360 KB |
Output is correct |
8 |
Correct |
241 ms |
102264 KB |
Output is correct |
9 |
Correct |
250 ms |
102224 KB |
Output is correct |
10 |
Correct |
244 ms |
102176 KB |
Output is correct |
11 |
Correct |
439 ms |
102260 KB |
Output is correct |
12 |
Correct |
6530 ms |
102296 KB |
Output is correct |
13 |
Correct |
6071 ms |
102204 KB |
Output is correct |
14 |
Correct |
3 ms |
2508 KB |
Output is correct |
15 |
Correct |
324 ms |
102356 KB |
Output is correct |
16 |
Correct |
364 ms |
102364 KB |
Output is correct |
17 |
Correct |
258 ms |
102272 KB |
Output is correct |
18 |
Correct |
250 ms |
102284 KB |
Output is correct |
19 |
Correct |
302 ms |
102316 KB |
Output is correct |
20 |
Correct |
268 ms |
102340 KB |
Output is correct |
21 |
Correct |
267 ms |
102176 KB |
Output is correct |
22 |
Correct |
350 ms |
102260 KB |
Output is correct |
23 |
Correct |
440 ms |
102296 KB |
Output is correct |
24 |
Correct |
850 ms |
102248 KB |
Output is correct |
25 |
Correct |
316 ms |
101616 KB |
Output is correct |
26 |
Correct |
375 ms |
102232 KB |
Output is correct |
27 |
Correct |
279 ms |
102244 KB |
Output is correct |
28 |
Correct |
272 ms |
102212 KB |
Output is correct |
29 |
Correct |
404 ms |
102224 KB |
Output is correct |
30 |
Correct |
276 ms |
102176 KB |
Output is correct |
31 |
Correct |
308 ms |
102208 KB |
Output is correct |
32 |
Correct |
530 ms |
102376 KB |
Output is correct |
33 |
Correct |
626 ms |
102352 KB |
Output is correct |
34 |
Correct |
1439 ms |
102340 KB |
Output is correct |
35 |
Correct |
890 ms |
102212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2508 KB |
Output is correct |
2 |
Correct |
2041 ms |
808900 KB |
Output is correct |
3 |
Correct |
1961 ms |
809684 KB |
Output is correct |
4 |
Correct |
1990 ms |
809996 KB |
Output is correct |
5 |
Correct |
2057 ms |
809924 KB |
Output is correct |
6 |
Correct |
2024 ms |
809664 KB |
Output is correct |
7 |
Correct |
1893 ms |
809784 KB |
Output is correct |
8 |
Correct |
3 ms |
2508 KB |
Output is correct |
9 |
Correct |
330 ms |
102228 KB |
Output is correct |
10 |
Correct |
270 ms |
102308 KB |
Output is correct |
11 |
Correct |
231 ms |
102260 KB |
Output is correct |
12 |
Correct |
249 ms |
102176 KB |
Output is correct |
13 |
Correct |
318 ms |
102344 KB |
Output is correct |
14 |
Correct |
592 ms |
102360 KB |
Output is correct |
15 |
Correct |
241 ms |
102264 KB |
Output is correct |
16 |
Correct |
250 ms |
102224 KB |
Output is correct |
17 |
Correct |
244 ms |
102176 KB |
Output is correct |
18 |
Correct |
439 ms |
102260 KB |
Output is correct |
19 |
Correct |
6530 ms |
102296 KB |
Output is correct |
20 |
Correct |
6071 ms |
102204 KB |
Output is correct |
21 |
Correct |
3 ms |
2508 KB |
Output is correct |
22 |
Correct |
324 ms |
102356 KB |
Output is correct |
23 |
Correct |
364 ms |
102364 KB |
Output is correct |
24 |
Correct |
258 ms |
102272 KB |
Output is correct |
25 |
Correct |
250 ms |
102284 KB |
Output is correct |
26 |
Correct |
302 ms |
102316 KB |
Output is correct |
27 |
Correct |
268 ms |
102340 KB |
Output is correct |
28 |
Correct |
267 ms |
102176 KB |
Output is correct |
29 |
Correct |
350 ms |
102260 KB |
Output is correct |
30 |
Correct |
440 ms |
102296 KB |
Output is correct |
31 |
Correct |
850 ms |
102248 KB |
Output is correct |
32 |
Correct |
316 ms |
101616 KB |
Output is correct |
33 |
Correct |
375 ms |
102232 KB |
Output is correct |
34 |
Correct |
279 ms |
102244 KB |
Output is correct |
35 |
Correct |
272 ms |
102212 KB |
Output is correct |
36 |
Correct |
404 ms |
102224 KB |
Output is correct |
37 |
Correct |
276 ms |
102176 KB |
Output is correct |
38 |
Correct |
308 ms |
102208 KB |
Output is correct |
39 |
Correct |
530 ms |
102376 KB |
Output is correct |
40 |
Correct |
626 ms |
102352 KB |
Output is correct |
41 |
Correct |
1439 ms |
102340 KB |
Output is correct |
42 |
Correct |
890 ms |
102212 KB |
Output is correct |
43 |
Correct |
1 ms |
436 KB |
Output is correct |
44 |
Correct |
4 ms |
2508 KB |
Output is correct |
45 |
Correct |
3709 ms |
814588 KB |
Output is correct |
46 |
Correct |
2422 ms |
813912 KB |
Output is correct |
47 |
Correct |
2414 ms |
813852 KB |
Output is correct |
48 |
Correct |
2033 ms |
814416 KB |
Output is correct |
49 |
Correct |
3673 ms |
814528 KB |
Output is correct |
50 |
Correct |
2029 ms |
814120 KB |
Output is correct |
51 |
Correct |
2144 ms |
814456 KB |
Output is correct |
52 |
Correct |
2178 ms |
813812 KB |
Output is correct |
53 |
Correct |
4011 ms |
813732 KB |
Output is correct |
54 |
Correct |
2814 ms |
813940 KB |
Output is correct |
55 |
Correct |
4097 ms |
813644 KB |
Output is correct |
56 |
Correct |
4813 ms |
813884 KB |
Output is correct |
57 |
Correct |
5926 ms |
813788 KB |
Output is correct |
58 |
Correct |
5264 ms |
814136 KB |
Output is correct |
59 |
Correct |
5124 ms |
814048 KB |
Output is correct |
60 |
Correct |
6083 ms |
813580 KB |
Output is correct |
61 |
Correct |
5678 ms |
813456 KB |
Output is correct |