#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
//we will use powers of 4 to decide what is the best jump
const int MAX_BIT = 13;
//jumps are base 4 to save memory
const int MAX_JUMP = 12;
const long long INF = 1e18;
vector<array<array<int, MAX_JUMP>, MAX_BIT>> jump;
vector<array<array<long long, MAX_JUMP>, MAX_BIT>> maxVal;
vector<array<array<long long, MAX_JUMP>, MAX_BIT>> sum;
int N;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
N = n;
vector<bool> vis(n+1, false);
jump.resize(n+1);
maxVal.resize(n+1);
sum.resize(n+1);
for(int i = 0; i < n; i++){
for(int bit = 0; bit < MAX_BIT; bit++){
if((1<<(2*bit)) >= s[i]){
jump[i][bit][0] = w[i];
maxVal[i][bit][0] = INF;
sum[i][bit][0] = s[i];
}else{
jump[i][bit][0] = l[i];
maxVal[i][bit][0] = s[i]-1;
sum[i][bit][0] = p[i];
}
}
}
for(int bit = 0; bit < MAX_BIT; bit++){
jump[n][bit][0] = n;
maxVal[n][bit][0] = INF;
sum[n][bit][0] = 0;
}
for(int l = 1; l < MAX_JUMP; l++){
for(int i = 0; i <= n; i++){
for(int bit = 0; bit < MAX_BIT; bit++){
int a, b, c, d;
a = jump[i][bit][l-1];
b = jump[a][bit][l-1];
c = jump[b][bit][l-1];
d = jump[c][bit][l-1];
jump[i][bit][l] = d;
sum[i][bit][l] = sum[i][bit][l-1] + sum[a][bit][l-1] + sum[b][bit][l-1] + sum[c][bit][l-1];
maxVal[i][bit][l] = min(min(maxVal[i][bit][l-1], maxVal[a][bit][l-1] - sum[i][bit][l-1]),min(maxVal[b][bit][l-1] - sum[a][bit][l-1] - sum[i][bit][l-1], maxVal[c][bit][l-1] - sum[b][bit][l-1] - sum[a][bit][l-1] - sum[i][bit][l-1]));
}
}
}
}
long long simulate(int x, int z){
long long val = z;
int bit = 0;
int xd = 1;
while(bit < MAX_BIT-1 && 4 * xd <= val){
bit++; xd *= 4;
}
while(x != N){
for(int i = MAX_JUMP-1; i >= 0; i--){
while(x != N && val <= maxVal[x][bit][i]){
val += sum[x][bit][i];
x = jump[x][bit][i];
}
}
if(x != N){
val += sum[x][MAX_BIT -1][0];
x = jump[x][MAX_BIT-1][0];
}
while(bit < MAX_BIT-1 && 4 * xd <= val){
bit++; xd *= 4;
}
}
return val;
}
/*
int main(){
int n, q; cin>>n>>q;
vector<int> s(n), p(n), w(n), l(n);
for(int i = 0; i < n; i++)cin>>s[i];
for(int i = 0; i < n; i++)cin>>p[i];
for(int i = 0; i < n; i++)cin>>w[i];
for(int i = 0; i < n; i++)cin>>l[i];
init(n, s, p, w, l);
for(int j = 0; j < q; j++){
int x, z; cin>>x>>z;
cout<<simulate(x, z)<<"\n";
}
}
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
11 ms |
6480 KB |
Output is correct |
4 |
Correct |
436 ms |
154552 KB |
Output is correct |
5 |
Correct |
8 ms |
6484 KB |
Output is correct |
6 |
Correct |
405 ms |
154468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
3839 ms |
1234808 KB |
Output is correct |
3 |
Correct |
4132 ms |
1235052 KB |
Output is correct |
4 |
Correct |
3448 ms |
1235048 KB |
Output is correct |
5 |
Correct |
2753 ms |
1234928 KB |
Output is correct |
6 |
Correct |
3695 ms |
1234892 KB |
Output is correct |
7 |
Correct |
3463 ms |
1234948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
442 ms |
155436 KB |
Output is correct |
3 |
Correct |
338 ms |
155512 KB |
Output is correct |
4 |
Correct |
334 ms |
155436 KB |
Output is correct |
5 |
Correct |
330 ms |
155216 KB |
Output is correct |
6 |
Correct |
419 ms |
155380 KB |
Output is correct |
7 |
Correct |
384 ms |
155384 KB |
Output is correct |
8 |
Correct |
334 ms |
155412 KB |
Output is correct |
9 |
Correct |
332 ms |
155340 KB |
Output is correct |
10 |
Correct |
318 ms |
155420 KB |
Output is correct |
11 |
Correct |
541 ms |
155260 KB |
Output is correct |
12 |
Correct |
796 ms |
155240 KB |
Output is correct |
13 |
Correct |
471 ms |
155340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
442 ms |
155436 KB |
Output is correct |
3 |
Correct |
338 ms |
155512 KB |
Output is correct |
4 |
Correct |
334 ms |
155436 KB |
Output is correct |
5 |
Correct |
330 ms |
155216 KB |
Output is correct |
6 |
Correct |
419 ms |
155380 KB |
Output is correct |
7 |
Correct |
384 ms |
155384 KB |
Output is correct |
8 |
Correct |
334 ms |
155412 KB |
Output is correct |
9 |
Correct |
332 ms |
155340 KB |
Output is correct |
10 |
Correct |
318 ms |
155420 KB |
Output is correct |
11 |
Correct |
541 ms |
155260 KB |
Output is correct |
12 |
Correct |
796 ms |
155240 KB |
Output is correct |
13 |
Correct |
471 ms |
155340 KB |
Output is correct |
14 |
Correct |
5 ms |
3412 KB |
Output is correct |
15 |
Correct |
360 ms |
155212 KB |
Output is correct |
16 |
Correct |
469 ms |
155380 KB |
Output is correct |
17 |
Correct |
385 ms |
155212 KB |
Output is correct |
18 |
Correct |
398 ms |
155300 KB |
Output is correct |
19 |
Correct |
441 ms |
155208 KB |
Output is correct |
20 |
Correct |
434 ms |
155328 KB |
Output is correct |
21 |
Correct |
417 ms |
155340 KB |
Output is correct |
22 |
Correct |
341 ms |
155192 KB |
Output is correct |
23 |
Correct |
567 ms |
155436 KB |
Output is correct |
24 |
Correct |
798 ms |
155372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
442 ms |
155436 KB |
Output is correct |
3 |
Correct |
338 ms |
155512 KB |
Output is correct |
4 |
Correct |
334 ms |
155436 KB |
Output is correct |
5 |
Correct |
330 ms |
155216 KB |
Output is correct |
6 |
Correct |
419 ms |
155380 KB |
Output is correct |
7 |
Correct |
384 ms |
155384 KB |
Output is correct |
8 |
Correct |
334 ms |
155412 KB |
Output is correct |
9 |
Correct |
332 ms |
155340 KB |
Output is correct |
10 |
Correct |
318 ms |
155420 KB |
Output is correct |
11 |
Correct |
541 ms |
155260 KB |
Output is correct |
12 |
Correct |
796 ms |
155240 KB |
Output is correct |
13 |
Correct |
471 ms |
155340 KB |
Output is correct |
14 |
Correct |
5 ms |
3412 KB |
Output is correct |
15 |
Correct |
360 ms |
155212 KB |
Output is correct |
16 |
Correct |
469 ms |
155380 KB |
Output is correct |
17 |
Correct |
385 ms |
155212 KB |
Output is correct |
18 |
Correct |
398 ms |
155300 KB |
Output is correct |
19 |
Correct |
441 ms |
155208 KB |
Output is correct |
20 |
Correct |
434 ms |
155328 KB |
Output is correct |
21 |
Correct |
417 ms |
155340 KB |
Output is correct |
22 |
Correct |
341 ms |
155192 KB |
Output is correct |
23 |
Correct |
567 ms |
155436 KB |
Output is correct |
24 |
Correct |
798 ms |
155372 KB |
Output is correct |
25 |
Correct |
506 ms |
154528 KB |
Output is correct |
26 |
Correct |
492 ms |
155304 KB |
Output is correct |
27 |
Correct |
414 ms |
155340 KB |
Output is correct |
28 |
Correct |
372 ms |
155244 KB |
Output is correct |
29 |
Correct |
511 ms |
155288 KB |
Output is correct |
30 |
Correct |
599 ms |
155348 KB |
Output is correct |
31 |
Correct |
579 ms |
155252 KB |
Output is correct |
32 |
Correct |
877 ms |
155324 KB |
Output is correct |
33 |
Correct |
1264 ms |
155244 KB |
Output is correct |
34 |
Correct |
1448 ms |
155156 KB |
Output is correct |
35 |
Correct |
857 ms |
155292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3412 KB |
Output is correct |
2 |
Correct |
3839 ms |
1234808 KB |
Output is correct |
3 |
Correct |
4132 ms |
1235052 KB |
Output is correct |
4 |
Correct |
3448 ms |
1235048 KB |
Output is correct |
5 |
Correct |
2753 ms |
1234928 KB |
Output is correct |
6 |
Correct |
3695 ms |
1234892 KB |
Output is correct |
7 |
Correct |
3463 ms |
1234948 KB |
Output is correct |
8 |
Correct |
4 ms |
3412 KB |
Output is correct |
9 |
Correct |
442 ms |
155436 KB |
Output is correct |
10 |
Correct |
338 ms |
155512 KB |
Output is correct |
11 |
Correct |
334 ms |
155436 KB |
Output is correct |
12 |
Correct |
330 ms |
155216 KB |
Output is correct |
13 |
Correct |
419 ms |
155380 KB |
Output is correct |
14 |
Correct |
384 ms |
155384 KB |
Output is correct |
15 |
Correct |
334 ms |
155412 KB |
Output is correct |
16 |
Correct |
332 ms |
155340 KB |
Output is correct |
17 |
Correct |
318 ms |
155420 KB |
Output is correct |
18 |
Correct |
541 ms |
155260 KB |
Output is correct |
19 |
Correct |
796 ms |
155240 KB |
Output is correct |
20 |
Correct |
471 ms |
155340 KB |
Output is correct |
21 |
Correct |
5 ms |
3412 KB |
Output is correct |
22 |
Correct |
360 ms |
155212 KB |
Output is correct |
23 |
Correct |
469 ms |
155380 KB |
Output is correct |
24 |
Correct |
385 ms |
155212 KB |
Output is correct |
25 |
Correct |
398 ms |
155300 KB |
Output is correct |
26 |
Correct |
441 ms |
155208 KB |
Output is correct |
27 |
Correct |
434 ms |
155328 KB |
Output is correct |
28 |
Correct |
417 ms |
155340 KB |
Output is correct |
29 |
Correct |
341 ms |
155192 KB |
Output is correct |
30 |
Correct |
567 ms |
155436 KB |
Output is correct |
31 |
Correct |
798 ms |
155372 KB |
Output is correct |
32 |
Correct |
506 ms |
154528 KB |
Output is correct |
33 |
Correct |
492 ms |
155304 KB |
Output is correct |
34 |
Correct |
414 ms |
155340 KB |
Output is correct |
35 |
Correct |
372 ms |
155244 KB |
Output is correct |
36 |
Correct |
511 ms |
155288 KB |
Output is correct |
37 |
Correct |
599 ms |
155348 KB |
Output is correct |
38 |
Correct |
579 ms |
155252 KB |
Output is correct |
39 |
Correct |
877 ms |
155324 KB |
Output is correct |
40 |
Correct |
1264 ms |
155244 KB |
Output is correct |
41 |
Correct |
1448 ms |
155156 KB |
Output is correct |
42 |
Correct |
857 ms |
155292 KB |
Output is correct |
43 |
Correct |
0 ms |
212 KB |
Output is correct |
44 |
Correct |
5 ms |
3432 KB |
Output is correct |
45 |
Correct |
5661 ms |
1235012 KB |
Output is correct |
46 |
Correct |
3862 ms |
1234988 KB |
Output is correct |
47 |
Correct |
3907 ms |
1234988 KB |
Output is correct |
48 |
Correct |
2655 ms |
1234972 KB |
Output is correct |
49 |
Correct |
6507 ms |
1235036 KB |
Output is correct |
50 |
Correct |
3692 ms |
1234860 KB |
Output is correct |
51 |
Correct |
2526 ms |
1234824 KB |
Output is correct |
52 |
Correct |
3805 ms |
1235960 KB |
Output is correct |
53 |
Execution timed out |
7103 ms |
1236048 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |