#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
private:
struct dAtA{
int to;
long long inc,thres;
dAtA(int go,int add,long long T){
to=go,inc=add,thres=T;
}
dAtA(){
to=0,inc=0,thres=0;
}
dAtA(dAtA a,dAtA b){
to=b.to;
inc=a.inc+b.inc;
thres=min(1ll*a.thres,b.thres-a.inc);
}
} bj[400100][24];
public:
long long strength(int n,int k){
return bj[n][k].inc;
}
long long thres(int n,int k){
return bj[n][k].thres;
}
int dungeon(int n,int k){
return bj[n][k].to;
}
void setdungeon(int n,int go,int add,long long T){
bj[n][0]=dAtA(go,add,T);
}
void preproc(int n){
for(int j=1;j<24;j++) for(int i=0;i<=n;i++)
bj[i][j]=dAtA(bj[i][j-1],bj[bj[i][j-1].to][j-1]);
}
} susss[9];
int l[400100],p[400100],s[400100],w[400100],fin;
long long pws[24];
int llog(int x){
for(int i=0;i<24;i++)
if(pws[i+1]>x)
return i;
}
void init(int n,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
fin=n;
pws[0]=1;
for(int i=1;i<24;i++)
pws[i]=pws[i-1]*10;
for(int i=0;i<n;i++) l[i]=L[i],p[i]=P[i],s[i]=S[i],w[i]=W[i];
for(int j=0;j<9;j++)
for(int i=0;i<n;i++) {
if(s[i]<=pws[j])
susss[j].setdungeon(i,w[i],s[i],1e18);
else susss[j].setdungeon(i,l[i],p[i],s[i]);
}
for(int i=0;i<9;i++)
susss[i].setdungeon(n,n,0,1e18),
susss[i].preproc(n);
}
long long simulate(int x, int Z) {
long long z=Z;
while(1){
int K=min(8,llog(z));
for(int i=24;i--;)
if(susss[K].thres(x,i)>z)
z+=susss[K].strength(x,i),
x=susss[K].dungeon(x,i);
if(x==fin) return z;
int k=s[x];
if(k<=z)
x=w[x],z+=k;
else x=l[x],z+=p[x];
if(x==fin) return z;
}
}
Compilation message
dungeons.cpp: In function 'int llog(int)':
dungeons.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
45 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
2031696 KB |
Output is correct |
2 |
Correct |
544 ms |
2031768 KB |
Output is correct |
3 |
Correct |
515 ms |
2031892 KB |
Output is correct |
4 |
Correct |
571 ms |
2034004 KB |
Output is correct |
5 |
Correct |
538 ms |
2031864 KB |
Output is correct |
6 |
Correct |
583 ms |
2034000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
499 ms |
2031952 KB |
Output is correct |
2 |
Correct |
1393 ms |
2050688 KB |
Output is correct |
3 |
Correct |
1372 ms |
2054956 KB |
Output is correct |
4 |
Correct |
1399 ms |
2055968 KB |
Output is correct |
5 |
Correct |
1318 ms |
2053948 KB |
Output is correct |
6 |
Correct |
1432 ms |
2053316 KB |
Output is correct |
7 |
Correct |
1323 ms |
2052124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
507 ms |
2031764 KB |
Output is correct |
2 |
Correct |
595 ms |
2034772 KB |
Output is correct |
3 |
Correct |
628 ms |
2034832 KB |
Output is correct |
4 |
Correct |
596 ms |
2035028 KB |
Output is correct |
5 |
Correct |
587 ms |
2034728 KB |
Output is correct |
6 |
Correct |
621 ms |
2034588 KB |
Output is correct |
7 |
Correct |
611 ms |
2034636 KB |
Output is correct |
8 |
Correct |
658 ms |
2034860 KB |
Output is correct |
9 |
Correct |
613 ms |
2034768 KB |
Output is correct |
10 |
Correct |
652 ms |
2034768 KB |
Output is correct |
11 |
Correct |
647 ms |
2034588 KB |
Output is correct |
12 |
Correct |
663 ms |
2034772 KB |
Output is correct |
13 |
Correct |
653 ms |
2034844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
507 ms |
2031764 KB |
Output is correct |
2 |
Correct |
595 ms |
2034772 KB |
Output is correct |
3 |
Correct |
628 ms |
2034832 KB |
Output is correct |
4 |
Correct |
596 ms |
2035028 KB |
Output is correct |
5 |
Correct |
587 ms |
2034728 KB |
Output is correct |
6 |
Correct |
621 ms |
2034588 KB |
Output is correct |
7 |
Correct |
611 ms |
2034636 KB |
Output is correct |
8 |
Correct |
658 ms |
2034860 KB |
Output is correct |
9 |
Correct |
613 ms |
2034768 KB |
Output is correct |
10 |
Correct |
652 ms |
2034768 KB |
Output is correct |
11 |
Correct |
647 ms |
2034588 KB |
Output is correct |
12 |
Correct |
663 ms |
2034772 KB |
Output is correct |
13 |
Correct |
653 ms |
2034844 KB |
Output is correct |
14 |
Correct |
556 ms |
2031696 KB |
Output is correct |
15 |
Correct |
621 ms |
2034772 KB |
Output is correct |
16 |
Correct |
656 ms |
2034628 KB |
Output is correct |
17 |
Correct |
619 ms |
2034772 KB |
Output is correct |
18 |
Correct |
625 ms |
2034636 KB |
Output is correct |
19 |
Correct |
609 ms |
2034720 KB |
Output is correct |
20 |
Correct |
617 ms |
2034772 KB |
Output is correct |
21 |
Correct |
622 ms |
2034768 KB |
Output is correct |
22 |
Correct |
602 ms |
2034768 KB |
Output is correct |
23 |
Correct |
601 ms |
2034768 KB |
Output is correct |
24 |
Correct |
652 ms |
2034772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
507 ms |
2031764 KB |
Output is correct |
2 |
Correct |
595 ms |
2034772 KB |
Output is correct |
3 |
Correct |
628 ms |
2034832 KB |
Output is correct |
4 |
Correct |
596 ms |
2035028 KB |
Output is correct |
5 |
Correct |
587 ms |
2034728 KB |
Output is correct |
6 |
Correct |
621 ms |
2034588 KB |
Output is correct |
7 |
Correct |
611 ms |
2034636 KB |
Output is correct |
8 |
Correct |
658 ms |
2034860 KB |
Output is correct |
9 |
Correct |
613 ms |
2034768 KB |
Output is correct |
10 |
Correct |
652 ms |
2034768 KB |
Output is correct |
11 |
Correct |
647 ms |
2034588 KB |
Output is correct |
12 |
Correct |
663 ms |
2034772 KB |
Output is correct |
13 |
Correct |
653 ms |
2034844 KB |
Output is correct |
14 |
Correct |
556 ms |
2031696 KB |
Output is correct |
15 |
Correct |
621 ms |
2034772 KB |
Output is correct |
16 |
Correct |
656 ms |
2034628 KB |
Output is correct |
17 |
Correct |
619 ms |
2034772 KB |
Output is correct |
18 |
Correct |
625 ms |
2034636 KB |
Output is correct |
19 |
Correct |
609 ms |
2034720 KB |
Output is correct |
20 |
Correct |
617 ms |
2034772 KB |
Output is correct |
21 |
Correct |
622 ms |
2034768 KB |
Output is correct |
22 |
Correct |
602 ms |
2034768 KB |
Output is correct |
23 |
Correct |
601 ms |
2034768 KB |
Output is correct |
24 |
Correct |
652 ms |
2034772 KB |
Output is correct |
25 |
Correct |
602 ms |
2034000 KB |
Output is correct |
26 |
Correct |
604 ms |
2034772 KB |
Output is correct |
27 |
Correct |
592 ms |
2034728 KB |
Output is correct |
28 |
Correct |
596 ms |
2034596 KB |
Output is correct |
29 |
Correct |
614 ms |
2034720 KB |
Output is correct |
30 |
Correct |
626 ms |
2034732 KB |
Output is correct |
31 |
Correct |
620 ms |
2034768 KB |
Output is correct |
32 |
Correct |
625 ms |
2034768 KB |
Output is correct |
33 |
Correct |
730 ms |
2034772 KB |
Output is correct |
34 |
Correct |
906 ms |
2034724 KB |
Output is correct |
35 |
Correct |
674 ms |
2034684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
499 ms |
2031952 KB |
Output is correct |
2 |
Correct |
1393 ms |
2050688 KB |
Output is correct |
3 |
Correct |
1372 ms |
2054956 KB |
Output is correct |
4 |
Correct |
1399 ms |
2055968 KB |
Output is correct |
5 |
Correct |
1318 ms |
2053948 KB |
Output is correct |
6 |
Correct |
1432 ms |
2053316 KB |
Output is correct |
7 |
Correct |
1323 ms |
2052124 KB |
Output is correct |
8 |
Correct |
507 ms |
2031764 KB |
Output is correct |
9 |
Correct |
595 ms |
2034772 KB |
Output is correct |
10 |
Correct |
628 ms |
2034832 KB |
Output is correct |
11 |
Correct |
596 ms |
2035028 KB |
Output is correct |
12 |
Correct |
587 ms |
2034728 KB |
Output is correct |
13 |
Correct |
621 ms |
2034588 KB |
Output is correct |
14 |
Correct |
611 ms |
2034636 KB |
Output is correct |
15 |
Correct |
658 ms |
2034860 KB |
Output is correct |
16 |
Correct |
613 ms |
2034768 KB |
Output is correct |
17 |
Correct |
652 ms |
2034768 KB |
Output is correct |
18 |
Correct |
647 ms |
2034588 KB |
Output is correct |
19 |
Correct |
663 ms |
2034772 KB |
Output is correct |
20 |
Correct |
653 ms |
2034844 KB |
Output is correct |
21 |
Correct |
556 ms |
2031696 KB |
Output is correct |
22 |
Correct |
621 ms |
2034772 KB |
Output is correct |
23 |
Correct |
656 ms |
2034628 KB |
Output is correct |
24 |
Correct |
619 ms |
2034772 KB |
Output is correct |
25 |
Correct |
625 ms |
2034636 KB |
Output is correct |
26 |
Correct |
609 ms |
2034720 KB |
Output is correct |
27 |
Correct |
617 ms |
2034772 KB |
Output is correct |
28 |
Correct |
622 ms |
2034768 KB |
Output is correct |
29 |
Correct |
602 ms |
2034768 KB |
Output is correct |
30 |
Correct |
601 ms |
2034768 KB |
Output is correct |
31 |
Correct |
652 ms |
2034772 KB |
Output is correct |
32 |
Correct |
602 ms |
2034000 KB |
Output is correct |
33 |
Correct |
604 ms |
2034772 KB |
Output is correct |
34 |
Correct |
592 ms |
2034728 KB |
Output is correct |
35 |
Correct |
596 ms |
2034596 KB |
Output is correct |
36 |
Correct |
614 ms |
2034720 KB |
Output is correct |
37 |
Correct |
626 ms |
2034732 KB |
Output is correct |
38 |
Correct |
620 ms |
2034768 KB |
Output is correct |
39 |
Correct |
625 ms |
2034768 KB |
Output is correct |
40 |
Correct |
730 ms |
2034772 KB |
Output is correct |
41 |
Correct |
906 ms |
2034724 KB |
Output is correct |
42 |
Correct |
674 ms |
2034684 KB |
Output is correct |
43 |
Correct |
746 ms |
2031828 KB |
Output is correct |
44 |
Correct |
535 ms |
2031956 KB |
Output is correct |
45 |
Correct |
1355 ms |
2061108 KB |
Output is correct |
46 |
Correct |
1275 ms |
2056500 KB |
Output is correct |
47 |
Correct |
1287 ms |
2056876 KB |
Output is correct |
48 |
Correct |
1293 ms |
2059056 KB |
Output is correct |
49 |
Correct |
1321 ms |
2061148 KB |
Output is correct |
50 |
Correct |
1407 ms |
2058676 KB |
Output is correct |
51 |
Correct |
1321 ms |
2059056 KB |
Output is correct |
52 |
Correct |
1394 ms |
2056756 KB |
Output is correct |
53 |
Correct |
1614 ms |
2057516 KB |
Output is correct |
54 |
Correct |
1705 ms |
2058668 KB |
Output is correct |
55 |
Correct |
2157 ms |
2057644 KB |
Output is correct |
56 |
Correct |
1540 ms |
2058292 KB |
Output is correct |
57 |
Correct |
1525 ms |
2058292 KB |
Output is correct |
58 |
Correct |
1607 ms |
2058416 KB |
Output is correct |
59 |
Correct |
1614 ms |
2058540 KB |
Output is correct |
60 |
Correct |
1991 ms |
2057780 KB |
Output is correct |
61 |
Correct |
1889 ms |
2057776 KB |
Output is correct |