#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=400000+10,lg=18,maxm=maxn*2;
long long sp[maxm][lg],wsp[maxm][lg],ezafsp[maxm][lg];
long long n,all[maxm],r[maxm],l[maxm],s[maxm],p[maxm],inf=1e15+5;
struct stbor{
long long tamam,ezaf,kam;
stbor(){
ezaf=0;
kam=inf;
}
}fakebor;
stbor boro(long long ind,long long now,long long len){
if(ind==n){
stbor ret;
ret.ezaf=now;
ret.kam=inf;
ret.tamam=ind;
return ret;
}
if(len==0){
stbor ret;
ret.ezaf=now;
ret.kam=inf;
ret.tamam=ind;
return ret;
}
long long ziad=now;
long long u=ind;
if(now>=s[ind]){
ziad-=s[ind];
}else{
u=ind+maxn;
}
stbor ret;
for(long long j=lg-1;j>=0;j--){
if((1<<j)<=len&&wsp[u][j]>ziad){
ret=boro(sp[u][j],ezafsp[u][j]+ziad,len-(1<<j));
ret.kam=min(ret.kam,wsp[u][j]-ziad);
return ret;
}
}
return ret;
}
void calsp(){
for(long long i=0;i<n;i++){
sp[i][0]=r[i];
wsp[i][0]=inf;
ezafsp[i][0]=s[i]+s[i];
sp[i+maxn][0]=l[i];
wsp[i+maxn][0]=inf;
wsp[i+maxn][0]=s[i];
ezafsp[i+maxn][0]=p[i];
}
sp[n][0]=n;
wsp[n][0]=inf;
ezafsp[n][0]=0;
for(long long lev=1;lev<lg;lev++){
for(long long i=0;i<=n;i++){
// cout<<i<<" "<<lev<<endl;
stbor tof=boro(sp[i][lev-1],ezafsp[i][lev-1],(1<<(lev-1)));
sp[i][lev]=tof.tamam;
wsp[i][lev]=min(wsp[i][lev-1],tof.kam);
ezafsp[i][lev]=tof.ezaf;
tof=boro(sp[i+maxn][lev-1],ezafsp[i+maxn][lev-1],(1<<(lev-1)));
sp[i+maxn][lev]=tof.tamam;
wsp[i+maxn][lev]=min(wsp[i+maxn][lev-1],tof.kam);
ezafsp[i+maxn][lev]=tof.ezaf;
}
}
}
void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
n=n_;
fakebor.tamam=n;
for(long long i=0;i<n;i++){
s[i]=s_[i];
l[i]=l_[i];
r[i]=w_[i];
p[i]=p_[i];
}
calsp();
return;
}
long long simulate(int x,int z) {
stbor ret=boro(x,z,1e9);
return ret.ezaf;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
1 ms |
18776 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
4 |
Correct |
36 ms |
65748 KB |
Output is correct |
5 |
Correct |
3 ms |
18780 KB |
Output is correct |
6 |
Correct |
47 ms |
65780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18780 KB |
Output is correct |
2 |
Correct |
2806 ms |
370680 KB |
Output is correct |
3 |
Correct |
3120 ms |
370916 KB |
Output is correct |
4 |
Correct |
3402 ms |
370912 KB |
Output is correct |
5 |
Correct |
551 ms |
370768 KB |
Output is correct |
6 |
Correct |
2750 ms |
370744 KB |
Output is correct |
7 |
Correct |
1308 ms |
370912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18780 KB |
Output is correct |
2 |
Correct |
59 ms |
66524 KB |
Output is correct |
3 |
Correct |
58 ms |
66396 KB |
Output is correct |
4 |
Correct |
56 ms |
66392 KB |
Output is correct |
5 |
Correct |
56 ms |
66396 KB |
Output is correct |
6 |
Correct |
62 ms |
66396 KB |
Output is correct |
7 |
Correct |
67 ms |
66392 KB |
Output is correct |
8 |
Correct |
59 ms |
66392 KB |
Output is correct |
9 |
Correct |
46 ms |
66392 KB |
Output is correct |
10 |
Correct |
59 ms |
66396 KB |
Output is correct |
11 |
Correct |
50 ms |
66392 KB |
Output is correct |
12 |
Correct |
142 ms |
66532 KB |
Output is correct |
13 |
Correct |
134 ms |
66396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18780 KB |
Output is correct |
2 |
Correct |
59 ms |
66524 KB |
Output is correct |
3 |
Correct |
58 ms |
66396 KB |
Output is correct |
4 |
Correct |
56 ms |
66392 KB |
Output is correct |
5 |
Correct |
56 ms |
66396 KB |
Output is correct |
6 |
Correct |
62 ms |
66396 KB |
Output is correct |
7 |
Correct |
67 ms |
66392 KB |
Output is correct |
8 |
Correct |
59 ms |
66392 KB |
Output is correct |
9 |
Correct |
46 ms |
66392 KB |
Output is correct |
10 |
Correct |
59 ms |
66396 KB |
Output is correct |
11 |
Correct |
50 ms |
66392 KB |
Output is correct |
12 |
Correct |
142 ms |
66532 KB |
Output is correct |
13 |
Correct |
134 ms |
66396 KB |
Output is correct |
14 |
Correct |
2 ms |
18780 KB |
Output is correct |
15 |
Correct |
82 ms |
66532 KB |
Output is correct |
16 |
Correct |
58 ms |
66396 KB |
Output is correct |
17 |
Correct |
62 ms |
66568 KB |
Output is correct |
18 |
Correct |
70 ms |
66568 KB |
Output is correct |
19 |
Correct |
59 ms |
66396 KB |
Output is correct |
20 |
Correct |
157 ms |
66396 KB |
Output is correct |
21 |
Correct |
123 ms |
66568 KB |
Output is correct |
22 |
Correct |
114 ms |
66392 KB |
Output is correct |
23 |
Correct |
54 ms |
66400 KB |
Output is correct |
24 |
Correct |
77 ms |
66596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18780 KB |
Output is correct |
2 |
Correct |
59 ms |
66524 KB |
Output is correct |
3 |
Correct |
58 ms |
66396 KB |
Output is correct |
4 |
Correct |
56 ms |
66392 KB |
Output is correct |
5 |
Correct |
56 ms |
66396 KB |
Output is correct |
6 |
Correct |
62 ms |
66396 KB |
Output is correct |
7 |
Correct |
67 ms |
66392 KB |
Output is correct |
8 |
Correct |
59 ms |
66392 KB |
Output is correct |
9 |
Correct |
46 ms |
66392 KB |
Output is correct |
10 |
Correct |
59 ms |
66396 KB |
Output is correct |
11 |
Correct |
50 ms |
66392 KB |
Output is correct |
12 |
Correct |
142 ms |
66532 KB |
Output is correct |
13 |
Correct |
134 ms |
66396 KB |
Output is correct |
14 |
Correct |
2 ms |
18780 KB |
Output is correct |
15 |
Correct |
82 ms |
66532 KB |
Output is correct |
16 |
Correct |
58 ms |
66396 KB |
Output is correct |
17 |
Correct |
62 ms |
66568 KB |
Output is correct |
18 |
Correct |
70 ms |
66568 KB |
Output is correct |
19 |
Correct |
59 ms |
66396 KB |
Output is correct |
20 |
Correct |
157 ms |
66396 KB |
Output is correct |
21 |
Correct |
123 ms |
66568 KB |
Output is correct |
22 |
Correct |
114 ms |
66392 KB |
Output is correct |
23 |
Correct |
54 ms |
66400 KB |
Output is correct |
24 |
Correct |
77 ms |
66596 KB |
Output is correct |
25 |
Correct |
41 ms |
65628 KB |
Output is correct |
26 |
Correct |
51 ms |
66396 KB |
Output is correct |
27 |
Correct |
134 ms |
66392 KB |
Output is correct |
28 |
Correct |
112 ms |
66392 KB |
Output is correct |
29 |
Correct |
55 ms |
66396 KB |
Output is correct |
30 |
Correct |
247 ms |
66532 KB |
Output is correct |
31 |
Correct |
293 ms |
66568 KB |
Output is correct |
32 |
Correct |
340 ms |
66564 KB |
Output is correct |
33 |
Correct |
105 ms |
66396 KB |
Output is correct |
34 |
Correct |
122 ms |
66396 KB |
Output is correct |
35 |
Correct |
208 ms |
66568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18780 KB |
Output is correct |
2 |
Correct |
2806 ms |
370680 KB |
Output is correct |
3 |
Correct |
3120 ms |
370916 KB |
Output is correct |
4 |
Correct |
3402 ms |
370912 KB |
Output is correct |
5 |
Correct |
551 ms |
370768 KB |
Output is correct |
6 |
Correct |
2750 ms |
370744 KB |
Output is correct |
7 |
Correct |
1308 ms |
370912 KB |
Output is correct |
8 |
Correct |
2 ms |
18780 KB |
Output is correct |
9 |
Correct |
59 ms |
66524 KB |
Output is correct |
10 |
Correct |
58 ms |
66396 KB |
Output is correct |
11 |
Correct |
56 ms |
66392 KB |
Output is correct |
12 |
Correct |
56 ms |
66396 KB |
Output is correct |
13 |
Correct |
62 ms |
66396 KB |
Output is correct |
14 |
Correct |
67 ms |
66392 KB |
Output is correct |
15 |
Correct |
59 ms |
66392 KB |
Output is correct |
16 |
Correct |
46 ms |
66392 KB |
Output is correct |
17 |
Correct |
59 ms |
66396 KB |
Output is correct |
18 |
Correct |
50 ms |
66392 KB |
Output is correct |
19 |
Correct |
142 ms |
66532 KB |
Output is correct |
20 |
Correct |
134 ms |
66396 KB |
Output is correct |
21 |
Correct |
2 ms |
18780 KB |
Output is correct |
22 |
Correct |
82 ms |
66532 KB |
Output is correct |
23 |
Correct |
58 ms |
66396 KB |
Output is correct |
24 |
Correct |
62 ms |
66568 KB |
Output is correct |
25 |
Correct |
70 ms |
66568 KB |
Output is correct |
26 |
Correct |
59 ms |
66396 KB |
Output is correct |
27 |
Correct |
157 ms |
66396 KB |
Output is correct |
28 |
Correct |
123 ms |
66568 KB |
Output is correct |
29 |
Correct |
114 ms |
66392 KB |
Output is correct |
30 |
Correct |
54 ms |
66400 KB |
Output is correct |
31 |
Correct |
77 ms |
66596 KB |
Output is correct |
32 |
Correct |
41 ms |
65628 KB |
Output is correct |
33 |
Correct |
51 ms |
66396 KB |
Output is correct |
34 |
Correct |
134 ms |
66392 KB |
Output is correct |
35 |
Correct |
112 ms |
66392 KB |
Output is correct |
36 |
Correct |
55 ms |
66396 KB |
Output is correct |
37 |
Correct |
247 ms |
66532 KB |
Output is correct |
38 |
Correct |
293 ms |
66568 KB |
Output is correct |
39 |
Correct |
340 ms |
66564 KB |
Output is correct |
40 |
Correct |
105 ms |
66396 KB |
Output is correct |
41 |
Correct |
122 ms |
66396 KB |
Output is correct |
42 |
Correct |
208 ms |
66568 KB |
Output is correct |
43 |
Correct |
2 ms |
18776 KB |
Output is correct |
44 |
Correct |
2 ms |
18780 KB |
Output is correct |
45 |
Correct |
565 ms |
370748 KB |
Output is correct |
46 |
Correct |
1647 ms |
370912 KB |
Output is correct |
47 |
Correct |
1082 ms |
370768 KB |
Output is correct |
48 |
Correct |
2306 ms |
370912 KB |
Output is correct |
49 |
Correct |
614 ms |
370748 KB |
Output is correct |
50 |
Correct |
2858 ms |
370916 KB |
Output is correct |
51 |
Correct |
637 ms |
371028 KB |
Output is correct |
52 |
Correct |
2790 ms |
370904 KB |
Output is correct |
53 |
Correct |
6729 ms |
370768 KB |
Output is correct |
54 |
Correct |
1280 ms |
380108 KB |
Output is correct |
55 |
Correct |
2055 ms |
379064 KB |
Output is correct |
56 |
Correct |
3314 ms |
379688 KB |
Output is correct |
57 |
Correct |
3033 ms |
379728 KB |
Output is correct |
58 |
Correct |
2909 ms |
379732 KB |
Output is correct |
59 |
Correct |
2555 ms |
379984 KB |
Output is correct |
60 |
Correct |
5352 ms |
379212 KB |
Output is correct |
61 |
Correct |
4880 ms |
378964 KB |
Output is correct |