#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 400005;
// baza 10
int N, putere[9];
pair<pair<long long, long long>,int>lca[nmax][24][9];
vector<int>S, W;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
putere[0] = 1;
for(int i=1;i<=8;i++) putere[i] = putere[i-1] * 8;
for(auto &it : w) ++it;
for(auto &it : l) ++it;
S = s; W = w;
N = n;
for(int j=0;j<=8;j++){
for(int i=1;i<=n;i++){
if(s[i - 1] < putere[j]){
lca[i][0][j].sc = w[i - 1];
lca[i][0][j].fr.fr = s[i - 1];
lca[i][0][j].fr.sc = -1e18;
}
else{
lca[i][0][j].sc = l[i - 1];
lca[i][0][j].fr.fr = p[i - 1];
lca[i][0][j].fr.sc = -s[i - 1];
}
}
}
for(int k=1;k<=23;k++){
for(int j=0;j<=8;j++){
for(int i=1;i<=n;i++){
lca[i][k][j].sc = lca[lca[i][k-1][j].sc][k-1][j].sc;
lca[i][k][j].fr.fr = lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.fr;
lca[i][k][j].fr.sc = max(lca[i][k-1][j].fr.sc, lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.sc);
}
}
}
}
long long simulate(int x, int z) {
int pos_curr = x + 1;
long long putere_curr = z;
int i = 0;
int t = 0;
while(pos_curr != N + 1){
if(t == 7){
i++;
t = 0;
}
for(int j=23;j>=0;j--){
if(lca[pos_curr][j][i].sc && lca[pos_curr][j][i].fr.sc + putere_curr < 0LL){
putere_curr += lca[pos_curr][j][i].fr.fr;
pos_curr = lca[pos_curr][j][i].sc;
}
}
if(pos_curr == N + 1) break;
else{
++t;
putere_curr += (long long)S[pos_curr - 1];
pos_curr = W[pos_curr - 1];
}
}
return putere_curr;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
312 KB |
Output is correct |
3 |
Correct |
9 ms |
10576 KB |
Output is correct |
4 |
Correct |
403 ms |
256940 KB |
Output is correct |
5 |
Correct |
10 ms |
10492 KB |
Output is correct |
6 |
Correct |
374 ms |
256804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
4038 ms |
2047376 KB |
Output is correct |
3 |
Correct |
3923 ms |
2047120 KB |
Output is correct |
4 |
Correct |
4157 ms |
2046828 KB |
Output is correct |
5 |
Correct |
3377 ms |
2046752 KB |
Output is correct |
6 |
Correct |
4003 ms |
2045992 KB |
Output is correct |
7 |
Correct |
4065 ms |
2045716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
521 ms |
256604 KB |
Output is correct |
3 |
Correct |
1353 ms |
256676 KB |
Output is correct |
4 |
Correct |
596 ms |
256716 KB |
Output is correct |
5 |
Correct |
675 ms |
256676 KB |
Output is correct |
6 |
Correct |
487 ms |
256668 KB |
Output is correct |
7 |
Correct |
459 ms |
256684 KB |
Output is correct |
8 |
Correct |
657 ms |
256680 KB |
Output is correct |
9 |
Correct |
512 ms |
256680 KB |
Output is correct |
10 |
Correct |
565 ms |
256748 KB |
Output is correct |
11 |
Correct |
605 ms |
256676 KB |
Output is correct |
12 |
Correct |
1290 ms |
256636 KB |
Output is correct |
13 |
Correct |
532 ms |
256684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
521 ms |
256604 KB |
Output is correct |
3 |
Correct |
1353 ms |
256676 KB |
Output is correct |
4 |
Correct |
596 ms |
256716 KB |
Output is correct |
5 |
Correct |
675 ms |
256676 KB |
Output is correct |
6 |
Correct |
487 ms |
256668 KB |
Output is correct |
7 |
Correct |
459 ms |
256684 KB |
Output is correct |
8 |
Correct |
657 ms |
256680 KB |
Output is correct |
9 |
Correct |
512 ms |
256680 KB |
Output is correct |
10 |
Correct |
565 ms |
256748 KB |
Output is correct |
11 |
Correct |
605 ms |
256676 KB |
Output is correct |
12 |
Correct |
1290 ms |
256636 KB |
Output is correct |
13 |
Correct |
532 ms |
256684 KB |
Output is correct |
14 |
Correct |
5 ms |
5460 KB |
Output is correct |
15 |
Correct |
589 ms |
256904 KB |
Output is correct |
16 |
Correct |
526 ms |
256904 KB |
Output is correct |
17 |
Correct |
918 ms |
256916 KB |
Output is correct |
18 |
Correct |
1000 ms |
256948 KB |
Output is correct |
19 |
Correct |
482 ms |
256904 KB |
Output is correct |
20 |
Correct |
809 ms |
256892 KB |
Output is correct |
21 |
Correct |
821 ms |
256868 KB |
Output is correct |
22 |
Correct |
589 ms |
256896 KB |
Output is correct |
23 |
Correct |
516 ms |
256928 KB |
Output is correct |
24 |
Correct |
1237 ms |
257004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
521 ms |
256604 KB |
Output is correct |
3 |
Correct |
1353 ms |
256676 KB |
Output is correct |
4 |
Correct |
596 ms |
256716 KB |
Output is correct |
5 |
Correct |
675 ms |
256676 KB |
Output is correct |
6 |
Correct |
487 ms |
256668 KB |
Output is correct |
7 |
Correct |
459 ms |
256684 KB |
Output is correct |
8 |
Correct |
657 ms |
256680 KB |
Output is correct |
9 |
Correct |
512 ms |
256680 KB |
Output is correct |
10 |
Correct |
565 ms |
256748 KB |
Output is correct |
11 |
Correct |
605 ms |
256676 KB |
Output is correct |
12 |
Correct |
1290 ms |
256636 KB |
Output is correct |
13 |
Correct |
532 ms |
256684 KB |
Output is correct |
14 |
Correct |
5 ms |
5460 KB |
Output is correct |
15 |
Correct |
589 ms |
256904 KB |
Output is correct |
16 |
Correct |
526 ms |
256904 KB |
Output is correct |
17 |
Correct |
918 ms |
256916 KB |
Output is correct |
18 |
Correct |
1000 ms |
256948 KB |
Output is correct |
19 |
Correct |
482 ms |
256904 KB |
Output is correct |
20 |
Correct |
809 ms |
256892 KB |
Output is correct |
21 |
Correct |
821 ms |
256868 KB |
Output is correct |
22 |
Correct |
589 ms |
256896 KB |
Output is correct |
23 |
Correct |
516 ms |
256928 KB |
Output is correct |
24 |
Correct |
1237 ms |
257004 KB |
Output is correct |
25 |
Correct |
395 ms |
256120 KB |
Output is correct |
26 |
Correct |
526 ms |
256672 KB |
Output is correct |
27 |
Correct |
560 ms |
256680 KB |
Output is correct |
28 |
Correct |
520 ms |
256800 KB |
Output is correct |
29 |
Correct |
543 ms |
256684 KB |
Output is correct |
30 |
Correct |
830 ms |
256728 KB |
Output is correct |
31 |
Correct |
809 ms |
256868 KB |
Output is correct |
32 |
Correct |
1235 ms |
257052 KB |
Output is correct |
33 |
Correct |
1804 ms |
257044 KB |
Output is correct |
34 |
Correct |
2210 ms |
257600 KB |
Output is correct |
35 |
Correct |
1117 ms |
257832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
4038 ms |
2047376 KB |
Output is correct |
3 |
Correct |
3923 ms |
2047120 KB |
Output is correct |
4 |
Correct |
4157 ms |
2046828 KB |
Output is correct |
5 |
Correct |
3377 ms |
2046752 KB |
Output is correct |
6 |
Correct |
4003 ms |
2045992 KB |
Output is correct |
7 |
Correct |
4065 ms |
2045716 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
521 ms |
256604 KB |
Output is correct |
10 |
Correct |
1353 ms |
256676 KB |
Output is correct |
11 |
Correct |
596 ms |
256716 KB |
Output is correct |
12 |
Correct |
675 ms |
256676 KB |
Output is correct |
13 |
Correct |
487 ms |
256668 KB |
Output is correct |
14 |
Correct |
459 ms |
256684 KB |
Output is correct |
15 |
Correct |
657 ms |
256680 KB |
Output is correct |
16 |
Correct |
512 ms |
256680 KB |
Output is correct |
17 |
Correct |
565 ms |
256748 KB |
Output is correct |
18 |
Correct |
605 ms |
256676 KB |
Output is correct |
19 |
Correct |
1290 ms |
256636 KB |
Output is correct |
20 |
Correct |
532 ms |
256684 KB |
Output is correct |
21 |
Correct |
5 ms |
5460 KB |
Output is correct |
22 |
Correct |
589 ms |
256904 KB |
Output is correct |
23 |
Correct |
526 ms |
256904 KB |
Output is correct |
24 |
Correct |
918 ms |
256916 KB |
Output is correct |
25 |
Correct |
1000 ms |
256948 KB |
Output is correct |
26 |
Correct |
482 ms |
256904 KB |
Output is correct |
27 |
Correct |
809 ms |
256892 KB |
Output is correct |
28 |
Correct |
821 ms |
256868 KB |
Output is correct |
29 |
Correct |
589 ms |
256896 KB |
Output is correct |
30 |
Correct |
516 ms |
256928 KB |
Output is correct |
31 |
Correct |
1237 ms |
257004 KB |
Output is correct |
32 |
Correct |
395 ms |
256120 KB |
Output is correct |
33 |
Correct |
526 ms |
256672 KB |
Output is correct |
34 |
Correct |
560 ms |
256680 KB |
Output is correct |
35 |
Correct |
520 ms |
256800 KB |
Output is correct |
36 |
Correct |
543 ms |
256684 KB |
Output is correct |
37 |
Correct |
830 ms |
256728 KB |
Output is correct |
38 |
Correct |
809 ms |
256868 KB |
Output is correct |
39 |
Correct |
1235 ms |
257052 KB |
Output is correct |
40 |
Correct |
1804 ms |
257044 KB |
Output is correct |
41 |
Correct |
2210 ms |
257600 KB |
Output is correct |
42 |
Correct |
1117 ms |
257832 KB |
Output is correct |
43 |
Correct |
0 ms |
212 KB |
Output is correct |
44 |
Correct |
5 ms |
5460 KB |
Output is correct |
45 |
Correct |
3947 ms |
2056752 KB |
Output is correct |
46 |
Correct |
3659 ms |
2052740 KB |
Output is correct |
47 |
Correct |
3907 ms |
2053124 KB |
Output is correct |
48 |
Correct |
4272 ms |
2055292 KB |
Output is correct |
49 |
Correct |
3962 ms |
2056848 KB |
Output is correct |
50 |
Correct |
3814 ms |
2055004 KB |
Output is correct |
51 |
Correct |
3445 ms |
2055328 KB |
Output is correct |
52 |
Correct |
3767 ms |
2052996 KB |
Output is correct |
53 |
Correct |
6118 ms |
2053880 KB |
Output is correct |
54 |
Correct |
5165 ms |
2054880 KB |
Output is correct |
55 |
Correct |
5904 ms |
2053920 KB |
Output is correct |
56 |
Correct |
5291 ms |
2054568 KB |
Output is correct |
57 |
Correct |
5875 ms |
2054676 KB |
Output is correct |
58 |
Correct |
5789 ms |
2054684 KB |
Output is correct |
59 |
Correct |
5638 ms |
2054812 KB |
Output is correct |
60 |
Correct |
6586 ms |
2054028 KB |
Output is correct |
61 |
Correct |
6736 ms |
2053944 KB |
Output is correct |