#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pairll;
#define N 100007
#define fr first
#define sc second
ll n,s[4*N],p[4*N],w[4*N],l[4*N],k[4*N],mx[4*N];
struct D{
ll mxs,mns,dp,ds,pw,pl;
}d[4*N][30];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n=_n+1;
for(int i=1;i<n;i++){
s[i]=_s[i-1];
p[i]=_p[i-1];
w[i]=_w[i-1]+1;
l[i]=_l[i-1]+1;
d[i][0]={s[i]+s[i],s[i]+p[i],p[i],s[i],w[i],l[i]};
}
for(int i=1;i<=27;i++){
for(int j=1;j<=n-1;j++){
d[j][i].mxs=max(d[d[j][i-1].pw][i-1].mxs,d[j][i-1].mxs+d[d[j][i-1].pw][i-1].ds);
d[j][i].mns=min(d[d[j][i-1].pl][i-1].mns,d[j][i-1].mns+d[d[j][i-1].pl][i-1].dp);
d[j][i].dp=d[j][i-1].dp+d[d[j][i-1].pl][i-1].dp;
d[j][i].ds=d[j][i-1].ds+d[d[j][i-1].pw][i-1].ds;
d[j][i].pw=d[d[j][i-1].pw][i-1].pw;
d[j][i].pl=d[d[j][i-1].pl][i-1].pl;
}
}
for(int i=n-1;i>=1;i--){
k[i]=k[w[i]]+s[i];
mx[i]=max(mx[w[i]],s[i]);
}
return ;
}
pairll S0(ll x,ll y){
for(int i=27;i>=0;i--){
if(d[x][i].mns>y+d[x][i].dp){
y+=d[x][i].dp;
x=d[x][i].pl;
}
}
return make_pair(x,y);
}
pairll S1(ll x,ll y){
for(int i=27;i>=0;i--){
if(d[x][i].mxs<=y+d[x][i].ds){
y+=d[x][i].ds;
x=d[x][i].pw;
}
}
return make_pair(x,y);
}
long long simulate(int _x, int _z) {
ll x=_x;
ll z=_z;
x++;
ll tp=0;
if(s[x]<=z)tp=1;
while(x!=0){
if(tp==0){
pairll m1=S0(x,z);
x=m1.fr;
z=m1.sc;
}else{
pairll m1=S1(x,z);
x=m1.fr;
z=m1.sc;
}
tp^=1;
}
return z;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
3284 KB |
Output is correct |
4 |
Correct |
61 ms |
75756 KB |
Output is correct |
5 |
Correct |
4 ms |
3388 KB |
Output is correct |
6 |
Correct |
61 ms |
75512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
661 ms |
602808 KB |
Output is correct |
3 |
Correct |
590 ms |
602792 KB |
Output is correct |
4 |
Correct |
587 ms |
604364 KB |
Output is correct |
5 |
Correct |
598 ms |
604320 KB |
Output is correct |
6 |
Correct |
665 ms |
602792 KB |
Output is correct |
7 |
Correct |
631 ms |
601012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
100 ms |
77072 KB |
Output is correct |
3 |
Correct |
93 ms |
77224 KB |
Output is correct |
4 |
Correct |
78 ms |
76576 KB |
Output is correct |
5 |
Correct |
82 ms |
76492 KB |
Output is correct |
6 |
Correct |
91 ms |
76764 KB |
Output is correct |
7 |
Correct |
91 ms |
76748 KB |
Output is correct |
8 |
Correct |
82 ms |
76484 KB |
Output is correct |
9 |
Correct |
83 ms |
76492 KB |
Output is correct |
10 |
Correct |
78 ms |
76328 KB |
Output is correct |
11 |
Correct |
102 ms |
76736 KB |
Output is correct |
12 |
Correct |
171 ms |
76856 KB |
Output is correct |
13 |
Correct |
154 ms |
76748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
100 ms |
77072 KB |
Output is correct |
3 |
Correct |
93 ms |
77224 KB |
Output is correct |
4 |
Correct |
78 ms |
76576 KB |
Output is correct |
5 |
Correct |
82 ms |
76492 KB |
Output is correct |
6 |
Correct |
91 ms |
76764 KB |
Output is correct |
7 |
Correct |
91 ms |
76748 KB |
Output is correct |
8 |
Correct |
82 ms |
76484 KB |
Output is correct |
9 |
Correct |
83 ms |
76492 KB |
Output is correct |
10 |
Correct |
78 ms |
76328 KB |
Output is correct |
11 |
Correct |
102 ms |
76736 KB |
Output is correct |
12 |
Correct |
171 ms |
76856 KB |
Output is correct |
13 |
Correct |
154 ms |
76748 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
202 ms |
76876 KB |
Output is correct |
16 |
Correct |
93 ms |
77248 KB |
Output is correct |
17 |
Correct |
80 ms |
76588 KB |
Output is correct |
18 |
Correct |
84 ms |
76704 KB |
Output is correct |
19 |
Correct |
97 ms |
76736 KB |
Output is correct |
20 |
Correct |
100 ms |
76476 KB |
Output is correct |
21 |
Correct |
91 ms |
76612 KB |
Output is correct |
22 |
Execution timed out |
7056 ms |
76604 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
100 ms |
77072 KB |
Output is correct |
3 |
Correct |
93 ms |
77224 KB |
Output is correct |
4 |
Correct |
78 ms |
76576 KB |
Output is correct |
5 |
Correct |
82 ms |
76492 KB |
Output is correct |
6 |
Correct |
91 ms |
76764 KB |
Output is correct |
7 |
Correct |
91 ms |
76748 KB |
Output is correct |
8 |
Correct |
82 ms |
76484 KB |
Output is correct |
9 |
Correct |
83 ms |
76492 KB |
Output is correct |
10 |
Correct |
78 ms |
76328 KB |
Output is correct |
11 |
Correct |
102 ms |
76736 KB |
Output is correct |
12 |
Correct |
171 ms |
76856 KB |
Output is correct |
13 |
Correct |
154 ms |
76748 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
202 ms |
76876 KB |
Output is correct |
16 |
Correct |
93 ms |
77248 KB |
Output is correct |
17 |
Correct |
80 ms |
76588 KB |
Output is correct |
18 |
Correct |
84 ms |
76704 KB |
Output is correct |
19 |
Correct |
97 ms |
76736 KB |
Output is correct |
20 |
Correct |
100 ms |
76476 KB |
Output is correct |
21 |
Correct |
91 ms |
76612 KB |
Output is correct |
22 |
Execution timed out |
7056 ms |
76604 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
661 ms |
602808 KB |
Output is correct |
3 |
Correct |
590 ms |
602792 KB |
Output is correct |
4 |
Correct |
587 ms |
604364 KB |
Output is correct |
5 |
Correct |
598 ms |
604320 KB |
Output is correct |
6 |
Correct |
665 ms |
602792 KB |
Output is correct |
7 |
Correct |
631 ms |
601012 KB |
Output is correct |
8 |
Correct |
2 ms |
1876 KB |
Output is correct |
9 |
Correct |
100 ms |
77072 KB |
Output is correct |
10 |
Correct |
93 ms |
77224 KB |
Output is correct |
11 |
Correct |
78 ms |
76576 KB |
Output is correct |
12 |
Correct |
82 ms |
76492 KB |
Output is correct |
13 |
Correct |
91 ms |
76764 KB |
Output is correct |
14 |
Correct |
91 ms |
76748 KB |
Output is correct |
15 |
Correct |
82 ms |
76484 KB |
Output is correct |
16 |
Correct |
83 ms |
76492 KB |
Output is correct |
17 |
Correct |
78 ms |
76328 KB |
Output is correct |
18 |
Correct |
102 ms |
76736 KB |
Output is correct |
19 |
Correct |
171 ms |
76856 KB |
Output is correct |
20 |
Correct |
154 ms |
76748 KB |
Output is correct |
21 |
Correct |
2 ms |
1876 KB |
Output is correct |
22 |
Correct |
202 ms |
76876 KB |
Output is correct |
23 |
Correct |
93 ms |
77248 KB |
Output is correct |
24 |
Correct |
80 ms |
76588 KB |
Output is correct |
25 |
Correct |
84 ms |
76704 KB |
Output is correct |
26 |
Correct |
97 ms |
76736 KB |
Output is correct |
27 |
Correct |
100 ms |
76476 KB |
Output is correct |
28 |
Correct |
91 ms |
76612 KB |
Output is correct |
29 |
Execution timed out |
7056 ms |
76604 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |