/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N_MAX = 400000;
const int N_BITS = 25;
const int S_QITS = 13;
int N;
int strength[N_MAX];
int winBonus[N_MAX];
int loseBonus[N_MAX];
int winEdge[N_MAX];
int loseEdge[N_MAX];
int last[S_QITS][N_BITS][N_MAX + 1];
ll bonus[S_QITS][N_BITS][N_MAX + 1];
int maxDiff[S_QITS][N_BITS][N_MAX + 1];
// maximum (bonus - strength) at some moment when we lost
void init (int _N, vector <int> _S, vector <int> _P, vector <int> _W, vector <int> _L) {
// Transfer input to global
N = _N;
for (int u = 0; u < N; u++) {
strength[u] = _S[u];
winBonus[u] = _S[u];
loseBonus[u] = _P[u];
winEdge[u] = _W[u];
loseEdge[u] = _L[u];
}
// Precompute jumps
for (int sqit = 0; sqit < S_QITS; sqit++) {
for (int nbit = 0; nbit < N_BITS; nbit++) {
last[sqit][nbit][N] = N;
bonus[sqit][nbit][N] = 0;
maxDiff[sqit][nbit][N] = INT_MIN;
}
}
for (int u = 0; u < N; u++) {
for (int sqit = 0; sqit < S_QITS; sqit++) {
if ((1 << (sqit * 2)) > strength[u]) {
last[sqit][0][u] = winEdge[u];
bonus[sqit][0][u] = winBonus[u];
maxDiff[sqit][0][u] = INT_MIN;
} else {
last[sqit][0][u] = loseEdge[u];
bonus[sqit][0][u] = loseBonus[u];
maxDiff[sqit][0][u] = 0 - strength[u];
}
}
}
for (int nbit = 1; nbit < N_BITS; nbit++) {
for (int u = 0; u < N; u++) {
for (int sqit = 0; sqit < S_QITS; sqit++) {
int v = last[sqit][nbit - 1][u];
last[sqit][nbit][u] = last[sqit][nbit - 1][v];
bonus[sqit][nbit][u] = bonus[sqit][nbit - 1][u] + bonus[sqit][nbit - 1][v];
ll aux = maxDiff[sqit][nbit - 1][v];
if (aux != INT_MIN) {
aux += bonus[sqit][nbit - 1][u];
}
aux = min((ll) 0, aux);
maxDiff[sqit][nbit][u] = max(maxDiff[sqit][nbit - 1][u], (int) aux);
}
}
}
}
ll simulate (int u, int initStrength) {
ll currStrength = initStrength;
while (u < N) {
int sqit = 0;
while (sqit + 1 < S_QITS && (1 << ((sqit + 1) * 2)) <= currStrength) {
sqit++;
}
for (int nbit = N_BITS - 1; nbit >= 0; nbit--) {
int maxd = maxDiff[sqit][nbit][u];
if (maxd == INT_MIN || currStrength + maxd < 0) {
currStrength += bonus[sqit][nbit][u];
u = last[sqit][nbit][u];
}
}
if (u == N) {
break;
}
if (currStrength >= strength[u]) {
currStrength += winBonus[u];
u = winEdge[u];
} else {
currStrength += loseBonus[u];
u = loseEdge[u];
}
}
return currStrength;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7508 KB |
Output is correct |
2 |
Correct |
5 ms |
7508 KB |
Output is correct |
3 |
Correct |
11 ms |
17748 KB |
Output is correct |
4 |
Correct |
366 ms |
264168 KB |
Output is correct |
5 |
Correct |
13 ms |
17776 KB |
Output is correct |
6 |
Correct |
392 ms |
264148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12628 KB |
Output is correct |
2 |
Correct |
2040 ms |
2056564 KB |
Output is correct |
3 |
Correct |
2360 ms |
2062464 KB |
Output is correct |
4 |
Correct |
2425 ms |
2063460 KB |
Output is correct |
5 |
Correct |
3134 ms |
2064292 KB |
Output is correct |
6 |
Correct |
2186 ms |
2063368 KB |
Output is correct |
7 |
Correct |
2416 ms |
2061796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
547 ms |
264916 KB |
Output is correct |
3 |
Correct |
343 ms |
264964 KB |
Output is correct |
4 |
Correct |
261 ms |
264948 KB |
Output is correct |
5 |
Correct |
244 ms |
265116 KB |
Output is correct |
6 |
Correct |
545 ms |
264984 KB |
Output is correct |
7 |
Correct |
552 ms |
265020 KB |
Output is correct |
8 |
Correct |
293 ms |
264888 KB |
Output is correct |
9 |
Correct |
352 ms |
264992 KB |
Output is correct |
10 |
Correct |
277 ms |
264912 KB |
Output is correct |
11 |
Correct |
513 ms |
264896 KB |
Output is correct |
12 |
Correct |
755 ms |
264916 KB |
Output is correct |
13 |
Correct |
383 ms |
265012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
547 ms |
264916 KB |
Output is correct |
3 |
Correct |
343 ms |
264964 KB |
Output is correct |
4 |
Correct |
261 ms |
264948 KB |
Output is correct |
5 |
Correct |
244 ms |
265116 KB |
Output is correct |
6 |
Correct |
545 ms |
264984 KB |
Output is correct |
7 |
Correct |
552 ms |
265020 KB |
Output is correct |
8 |
Correct |
293 ms |
264888 KB |
Output is correct |
9 |
Correct |
352 ms |
264992 KB |
Output is correct |
10 |
Correct |
277 ms |
264912 KB |
Output is correct |
11 |
Correct |
513 ms |
264896 KB |
Output is correct |
12 |
Correct |
755 ms |
264916 KB |
Output is correct |
13 |
Correct |
383 ms |
265012 KB |
Output is correct |
14 |
Correct |
11 ms |
12628 KB |
Output is correct |
15 |
Correct |
417 ms |
265080 KB |
Output is correct |
16 |
Correct |
520 ms |
264928 KB |
Output is correct |
17 |
Correct |
308 ms |
265024 KB |
Output is correct |
18 |
Correct |
294 ms |
264924 KB |
Output is correct |
19 |
Correct |
557 ms |
264908 KB |
Output is correct |
20 |
Correct |
332 ms |
264904 KB |
Output is correct |
21 |
Correct |
343 ms |
264976 KB |
Output is correct |
22 |
Correct |
275 ms |
265088 KB |
Output is correct |
23 |
Correct |
554 ms |
264912 KB |
Output is correct |
24 |
Correct |
814 ms |
264984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
547 ms |
264916 KB |
Output is correct |
3 |
Correct |
343 ms |
264964 KB |
Output is correct |
4 |
Correct |
261 ms |
264948 KB |
Output is correct |
5 |
Correct |
244 ms |
265116 KB |
Output is correct |
6 |
Correct |
545 ms |
264984 KB |
Output is correct |
7 |
Correct |
552 ms |
265020 KB |
Output is correct |
8 |
Correct |
293 ms |
264888 KB |
Output is correct |
9 |
Correct |
352 ms |
264992 KB |
Output is correct |
10 |
Correct |
277 ms |
264912 KB |
Output is correct |
11 |
Correct |
513 ms |
264896 KB |
Output is correct |
12 |
Correct |
755 ms |
264916 KB |
Output is correct |
13 |
Correct |
383 ms |
265012 KB |
Output is correct |
14 |
Correct |
11 ms |
12628 KB |
Output is correct |
15 |
Correct |
417 ms |
265080 KB |
Output is correct |
16 |
Correct |
520 ms |
264928 KB |
Output is correct |
17 |
Correct |
308 ms |
265024 KB |
Output is correct |
18 |
Correct |
294 ms |
264924 KB |
Output is correct |
19 |
Correct |
557 ms |
264908 KB |
Output is correct |
20 |
Correct |
332 ms |
264904 KB |
Output is correct |
21 |
Correct |
343 ms |
264976 KB |
Output is correct |
22 |
Correct |
275 ms |
265088 KB |
Output is correct |
23 |
Correct |
554 ms |
264912 KB |
Output is correct |
24 |
Correct |
814 ms |
264984 KB |
Output is correct |
25 |
Correct |
458 ms |
264224 KB |
Output is correct |
26 |
Correct |
484 ms |
265104 KB |
Output is correct |
27 |
Correct |
397 ms |
264996 KB |
Output is correct |
28 |
Correct |
374 ms |
265064 KB |
Output is correct |
29 |
Correct |
485 ms |
264920 KB |
Output is correct |
30 |
Correct |
327 ms |
264980 KB |
Output is correct |
31 |
Correct |
328 ms |
264912 KB |
Output is correct |
32 |
Correct |
732 ms |
264904 KB |
Output is correct |
33 |
Correct |
954 ms |
264888 KB |
Output is correct |
34 |
Correct |
1548 ms |
264792 KB |
Output is correct |
35 |
Correct |
1018 ms |
264888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12628 KB |
Output is correct |
2 |
Correct |
2040 ms |
2056564 KB |
Output is correct |
3 |
Correct |
2360 ms |
2062464 KB |
Output is correct |
4 |
Correct |
2425 ms |
2063460 KB |
Output is correct |
5 |
Correct |
3134 ms |
2064292 KB |
Output is correct |
6 |
Correct |
2186 ms |
2063368 KB |
Output is correct |
7 |
Correct |
2416 ms |
2061796 KB |
Output is correct |
8 |
Correct |
9 ms |
12672 KB |
Output is correct |
9 |
Correct |
547 ms |
264916 KB |
Output is correct |
10 |
Correct |
343 ms |
264964 KB |
Output is correct |
11 |
Correct |
261 ms |
264948 KB |
Output is correct |
12 |
Correct |
244 ms |
265116 KB |
Output is correct |
13 |
Correct |
545 ms |
264984 KB |
Output is correct |
14 |
Correct |
552 ms |
265020 KB |
Output is correct |
15 |
Correct |
293 ms |
264888 KB |
Output is correct |
16 |
Correct |
352 ms |
264992 KB |
Output is correct |
17 |
Correct |
277 ms |
264912 KB |
Output is correct |
18 |
Correct |
513 ms |
264896 KB |
Output is correct |
19 |
Correct |
755 ms |
264916 KB |
Output is correct |
20 |
Correct |
383 ms |
265012 KB |
Output is correct |
21 |
Correct |
11 ms |
12628 KB |
Output is correct |
22 |
Correct |
417 ms |
265080 KB |
Output is correct |
23 |
Correct |
520 ms |
264928 KB |
Output is correct |
24 |
Correct |
308 ms |
265024 KB |
Output is correct |
25 |
Correct |
294 ms |
264924 KB |
Output is correct |
26 |
Correct |
557 ms |
264908 KB |
Output is correct |
27 |
Correct |
332 ms |
264904 KB |
Output is correct |
28 |
Correct |
343 ms |
264976 KB |
Output is correct |
29 |
Correct |
275 ms |
265088 KB |
Output is correct |
30 |
Correct |
554 ms |
264912 KB |
Output is correct |
31 |
Correct |
814 ms |
264984 KB |
Output is correct |
32 |
Correct |
458 ms |
264224 KB |
Output is correct |
33 |
Correct |
484 ms |
265104 KB |
Output is correct |
34 |
Correct |
397 ms |
264996 KB |
Output is correct |
35 |
Correct |
374 ms |
265064 KB |
Output is correct |
36 |
Correct |
485 ms |
264920 KB |
Output is correct |
37 |
Correct |
327 ms |
264980 KB |
Output is correct |
38 |
Correct |
328 ms |
264912 KB |
Output is correct |
39 |
Correct |
732 ms |
264904 KB |
Output is correct |
40 |
Correct |
954 ms |
264888 KB |
Output is correct |
41 |
Correct |
1548 ms |
264792 KB |
Output is correct |
42 |
Correct |
1018 ms |
264888 KB |
Output is correct |
43 |
Correct |
4 ms |
7508 KB |
Output is correct |
44 |
Correct |
9 ms |
12616 KB |
Output is correct |
45 |
Correct |
5460 ms |
2065136 KB |
Output is correct |
46 |
Correct |
3114 ms |
2063604 KB |
Output is correct |
47 |
Correct |
3145 ms |
2064008 KB |
Output is correct |
48 |
Correct |
2547 ms |
2065824 KB |
Output is correct |
49 |
Correct |
5205 ms |
2065584 KB |
Output is correct |
50 |
Correct |
1964 ms |
2065248 KB |
Output is correct |
51 |
Correct |
2702 ms |
2065092 KB |
Output is correct |
52 |
Correct |
1960 ms |
2063916 KB |
Output is correct |
53 |
Correct |
5215 ms |
2064716 KB |
Output is correct |
54 |
Correct |
3021 ms |
2064540 KB |
Output is correct |
55 |
Correct |
3589 ms |
2064340 KB |
Output is correct |
56 |
Correct |
5789 ms |
2063964 KB |
Output is correct |
57 |
Correct |
5687 ms |
2063856 KB |
Output is correct |
58 |
Correct |
6024 ms |
2063632 KB |
Output is correct |
59 |
Correct |
5964 ms |
2065656 KB |
Output is correct |
60 |
Correct |
4685 ms |
2064868 KB |
Output is correct |
61 |
Correct |
3186 ms |
2064896 KB |
Output is correct |