#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace ns{
int n,m;
int s[400005],p[400005],w[400005],l[400005];
int toe[400005];
//int f[21][400005],g[21][400005],h[21][400005];
struct arr{
signed v[400005];
signed &operator [](int b){return v[b];}
};
arr tb[505],*f[12],*g[12],*h[12],*las=tb;
arr *neww(int n){
arr *ret=las;las+=n;return ret;
}
int a[400005];
const signed inf=0x3f3f3f3f;
int pw[25];
void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
n=N;
for(int i=0;i<n;++i)s[i]=S[i],p[i]=P[i],w[i]=W[i],l[i]=L[i];
/*for(int i=0;i<n;++i)a[i+1]=s[i];
sort(a+1,a+n+1);
m=unique(a+1,a+n+1)-a-1;
for(int v=0;v<=m;++v){
for(int i=0;i<n;++i){
f[v][0][i]=(s[i]<=a[v]?w[i]:l[i]);
g[v][0][i]=(s[i]<=a[v]?s[i]:p[i]);
}
f[v][0][n]=n;g[v][0][n]=0;
for(int i=1;i<=30;++i)for(int j=0;j<=n;++j){
f[v][i][j]=f[v][i-1][f[v][i-1][j]];
g[v][i][j]=g[v][i-1][j]+g[v][i-1][f[v][i-1][j]];
}
}*/
for(int i=n-1;~i;--i)toe[i]=s[i]+toe[w[i]];
for(int i=0;i<=12;++i)pw[i]=1<<(i+i);
for(int v=0;v<12;++v){
f[v]=neww(v+v+2);
g[v]=neww(v+v+2);
h[v]=neww(v+v+2);
for(int i=0;i<n;++i){
if(s[i]<pw[v]){
f[v][0][i]=w[i];
g[v][0][i]=s[i];
h[v][0][i]=inf;
}
else{
f[v][0][i]=l[i];
g[v][0][i]=p[i];
h[v][0][i]=s[i];
}
}
f[v][0][n]=n;g[v][0][n]=0;h[v][0][n]=inf;
for(int i=1;i<=v+v+1;++i){
for(int j=0;j<=n;++j){
f[v][i][j]=f[v][i-1][f[v][i-1][j]];
g[v][i][j]=min(g[v][i-1][j]+g[v][i-1][f[v][i-1][j]],inf);
h[v][i][j]=max(min(h[v][i-1][j],h[v][i-1][f[v][i-1][j]]-g[v][i-1][j]),-1);
}
}
}
/*for(int i=0;i<n;++i){
f[0][i]=w[i],g[0][i]=s[i],h[0][i]=s[i];
}
f[0][n]=n;g[0][n]=h[0][n]=0;
for(int i=1;i<=20;++i){
for(int j=0;j<=n;++j){
f[i][j]=f[i-1][f[i-1][j]];
g[i][j]=max(g[i-1][j],g[i-1][f[i-1][j]]-h[i-1][j]);
h[i][j]=h[i-1][j]+h[i-1][f[i-1][j]];
}
}*/
}
long long simulate(int x, int z) {
int rk=0;
while(x<n){
if(z>=pw[rk+1]&&rk<12)++rk;
if(rk==12){
return z+toe[x];
}
for(int i=rk+rk+1;~i;--i){
if(z<h[rk][i][x] && g[rk][i][x]+z<pw[rk+1]){
z+=g[rk][i][x];
x=f[rk][i][x];
}
}
if(x<n){
if(z>=s[x]){
z+=s[x];x=w[x];
}
else{
z+=p[x];x=l[x];
}
}
}
return z;
/*while(x<n){
for(int i=20;~i;--i){
if(z>=g[i][x]){
z+=h[i][x];
x=f[i][x];
}
}
if(x<n){
z+=p[x];x=l[x];
}
}*/
/* if(z>=s[x]){
z+=s[x];x=w[x];
}
else{
z+=p[x];x=l[x];
}
}*/
return z ;
}
}
void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
ns::init(N,S,P,W,L);
}
long long simulate(signed x, signed z) {
return ns::simulate(x,z);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3532 KB |
Output is correct |
2 |
Correct |
2 ms |
3532 KB |
Output is correct |
3 |
Correct |
6 ms |
7364 KB |
Output is correct |
4 |
Correct |
93 ms |
99352 KB |
Output is correct |
5 |
Correct |
6 ms |
7456 KB |
Output is correct |
6 |
Correct |
95 ms |
99256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5452 KB |
Output is correct |
2 |
Correct |
1676 ms |
768160 KB |
Output is correct |
3 |
Correct |
1354 ms |
774880 KB |
Output is correct |
4 |
Correct |
1420 ms |
775464 KB |
Output is correct |
5 |
Correct |
991 ms |
775472 KB |
Output is correct |
6 |
Correct |
1786 ms |
774360 KB |
Output is correct |
7 |
Correct |
1491 ms |
772344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5580 KB |
Output is correct |
2 |
Correct |
202 ms |
100568 KB |
Output is correct |
3 |
Correct |
355 ms |
100564 KB |
Output is correct |
4 |
Correct |
425 ms |
100560 KB |
Output is correct |
5 |
Correct |
536 ms |
100556 KB |
Output is correct |
6 |
Correct |
608 ms |
100036 KB |
Output is correct |
7 |
Correct |
826 ms |
101316 KB |
Output is correct |
8 |
Correct |
568 ms |
101088 KB |
Output is correct |
9 |
Correct |
206 ms |
101188 KB |
Output is correct |
10 |
Correct |
496 ms |
100928 KB |
Output is correct |
11 |
Correct |
485 ms |
101444 KB |
Output is correct |
12 |
Correct |
1351 ms |
101308 KB |
Output is correct |
13 |
Correct |
1461 ms |
101312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5580 KB |
Output is correct |
2 |
Correct |
202 ms |
100568 KB |
Output is correct |
3 |
Correct |
355 ms |
100564 KB |
Output is correct |
4 |
Correct |
425 ms |
100560 KB |
Output is correct |
5 |
Correct |
536 ms |
100556 KB |
Output is correct |
6 |
Correct |
608 ms |
100036 KB |
Output is correct |
7 |
Correct |
826 ms |
101316 KB |
Output is correct |
8 |
Correct |
568 ms |
101088 KB |
Output is correct |
9 |
Correct |
206 ms |
101188 KB |
Output is correct |
10 |
Correct |
496 ms |
100928 KB |
Output is correct |
11 |
Correct |
485 ms |
101444 KB |
Output is correct |
12 |
Correct |
1351 ms |
101308 KB |
Output is correct |
13 |
Correct |
1461 ms |
101312 KB |
Output is correct |
14 |
Correct |
5 ms |
5580 KB |
Output is correct |
15 |
Correct |
245 ms |
101448 KB |
Output is correct |
16 |
Correct |
211 ms |
101672 KB |
Output is correct |
17 |
Correct |
499 ms |
101040 KB |
Output is correct |
18 |
Correct |
475 ms |
101088 KB |
Output is correct |
19 |
Correct |
679 ms |
101316 KB |
Output is correct |
20 |
Correct |
526 ms |
101040 KB |
Output is correct |
21 |
Correct |
554 ms |
101064 KB |
Output is correct |
22 |
Correct |
463 ms |
101316 KB |
Output is correct |
23 |
Correct |
627 ms |
101324 KB |
Output is correct |
24 |
Correct |
949 ms |
101284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5580 KB |
Output is correct |
2 |
Correct |
202 ms |
100568 KB |
Output is correct |
3 |
Correct |
355 ms |
100564 KB |
Output is correct |
4 |
Correct |
425 ms |
100560 KB |
Output is correct |
5 |
Correct |
536 ms |
100556 KB |
Output is correct |
6 |
Correct |
608 ms |
100036 KB |
Output is correct |
7 |
Correct |
826 ms |
101316 KB |
Output is correct |
8 |
Correct |
568 ms |
101088 KB |
Output is correct |
9 |
Correct |
206 ms |
101188 KB |
Output is correct |
10 |
Correct |
496 ms |
100928 KB |
Output is correct |
11 |
Correct |
485 ms |
101444 KB |
Output is correct |
12 |
Correct |
1351 ms |
101308 KB |
Output is correct |
13 |
Correct |
1461 ms |
101312 KB |
Output is correct |
14 |
Correct |
5 ms |
5580 KB |
Output is correct |
15 |
Correct |
245 ms |
101448 KB |
Output is correct |
16 |
Correct |
211 ms |
101672 KB |
Output is correct |
17 |
Correct |
499 ms |
101040 KB |
Output is correct |
18 |
Correct |
475 ms |
101088 KB |
Output is correct |
19 |
Correct |
679 ms |
101316 KB |
Output is correct |
20 |
Correct |
526 ms |
101040 KB |
Output is correct |
21 |
Correct |
554 ms |
101064 KB |
Output is correct |
22 |
Correct |
463 ms |
101316 KB |
Output is correct |
23 |
Correct |
627 ms |
101324 KB |
Output is correct |
24 |
Correct |
949 ms |
101284 KB |
Output is correct |
25 |
Correct |
121 ms |
100668 KB |
Output is correct |
26 |
Correct |
245 ms |
101572 KB |
Output is correct |
27 |
Correct |
224 ms |
101048 KB |
Output is correct |
28 |
Correct |
248 ms |
101060 KB |
Output is correct |
29 |
Correct |
260 ms |
101572 KB |
Output is correct |
30 |
Correct |
541 ms |
101276 KB |
Output is correct |
31 |
Correct |
548 ms |
101180 KB |
Output is correct |
32 |
Correct |
887 ms |
101316 KB |
Output is correct |
33 |
Correct |
783 ms |
101356 KB |
Output is correct |
34 |
Correct |
1538 ms |
101192 KB |
Output is correct |
35 |
Correct |
779 ms |
101268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5452 KB |
Output is correct |
2 |
Correct |
1676 ms |
768160 KB |
Output is correct |
3 |
Correct |
1354 ms |
774880 KB |
Output is correct |
4 |
Correct |
1420 ms |
775464 KB |
Output is correct |
5 |
Correct |
991 ms |
775472 KB |
Output is correct |
6 |
Correct |
1786 ms |
774360 KB |
Output is correct |
7 |
Correct |
1491 ms |
772344 KB |
Output is correct |
8 |
Correct |
5 ms |
5580 KB |
Output is correct |
9 |
Correct |
202 ms |
100568 KB |
Output is correct |
10 |
Correct |
355 ms |
100564 KB |
Output is correct |
11 |
Correct |
425 ms |
100560 KB |
Output is correct |
12 |
Correct |
536 ms |
100556 KB |
Output is correct |
13 |
Correct |
608 ms |
100036 KB |
Output is correct |
14 |
Correct |
826 ms |
101316 KB |
Output is correct |
15 |
Correct |
568 ms |
101088 KB |
Output is correct |
16 |
Correct |
206 ms |
101188 KB |
Output is correct |
17 |
Correct |
496 ms |
100928 KB |
Output is correct |
18 |
Correct |
485 ms |
101444 KB |
Output is correct |
19 |
Correct |
1351 ms |
101308 KB |
Output is correct |
20 |
Correct |
1461 ms |
101312 KB |
Output is correct |
21 |
Correct |
5 ms |
5580 KB |
Output is correct |
22 |
Correct |
245 ms |
101448 KB |
Output is correct |
23 |
Correct |
211 ms |
101672 KB |
Output is correct |
24 |
Correct |
499 ms |
101040 KB |
Output is correct |
25 |
Correct |
475 ms |
101088 KB |
Output is correct |
26 |
Correct |
679 ms |
101316 KB |
Output is correct |
27 |
Correct |
526 ms |
101040 KB |
Output is correct |
28 |
Correct |
554 ms |
101064 KB |
Output is correct |
29 |
Correct |
463 ms |
101316 KB |
Output is correct |
30 |
Correct |
627 ms |
101324 KB |
Output is correct |
31 |
Correct |
949 ms |
101284 KB |
Output is correct |
32 |
Correct |
121 ms |
100668 KB |
Output is correct |
33 |
Correct |
245 ms |
101572 KB |
Output is correct |
34 |
Correct |
224 ms |
101048 KB |
Output is correct |
35 |
Correct |
248 ms |
101060 KB |
Output is correct |
36 |
Correct |
260 ms |
101572 KB |
Output is correct |
37 |
Correct |
541 ms |
101276 KB |
Output is correct |
38 |
Correct |
548 ms |
101180 KB |
Output is correct |
39 |
Correct |
887 ms |
101316 KB |
Output is correct |
40 |
Correct |
783 ms |
101356 KB |
Output is correct |
41 |
Correct |
1538 ms |
101192 KB |
Output is correct |
42 |
Correct |
779 ms |
101268 KB |
Output is correct |
43 |
Correct |
3 ms |
3532 KB |
Output is correct |
44 |
Correct |
5 ms |
5488 KB |
Output is correct |
45 |
Correct |
1489 ms |
774092 KB |
Output is correct |
46 |
Correct |
1066 ms |
774664 KB |
Output is correct |
47 |
Correct |
1111 ms |
774332 KB |
Output is correct |
48 |
Correct |
1069 ms |
774076 KB |
Output is correct |
49 |
Correct |
1413 ms |
773240 KB |
Output is correct |
50 |
Correct |
1419 ms |
772644 KB |
Output is correct |
51 |
Correct |
1024 ms |
772528 KB |
Output is correct |
52 |
Correct |
1522 ms |
772284 KB |
Output is correct |
53 |
Correct |
2550 ms |
773104 KB |
Output is correct |
54 |
Correct |
1953 ms |
772504 KB |
Output is correct |
55 |
Correct |
2467 ms |
773996 KB |
Output is correct |
56 |
Correct |
2484 ms |
774020 KB |
Output is correct |
57 |
Correct |
2419 ms |
773976 KB |
Output is correct |
58 |
Correct |
2768 ms |
773712 KB |
Output is correct |
59 |
Correct |
2441 ms |
773088 KB |
Output is correct |
60 |
Correct |
2005 ms |
772920 KB |
Output is correct |
61 |
Correct |
1843 ms |
773244 KB |
Output is correct |