#include <bits/stdc++.h>
#include "dungeons.h"
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=400'000+1;
const int lt=19;
const int c=6;
int up[N][c][lt];
int mn[N][c][lt];
int go[N][c][lt];
ll pode[N];
int ok=0;
int w[N],s[N],p[N],l[N];
int n;
vec<int> kek;
vec<int> ps;
void clever_init(){
int pw=32;
ps.pb(1);
while(ps.back()<=(1e7)) ps.pb(ps.back()*pw);
int lv=sz(ps);
for(int i=n;i>=0;i--){
pode[i]=pode[w[i]]+s[i];
}
// cout<<lv<<endl;
for(int j=0;j+1<lv;j++){
for(int i=0;i<=n;i++){
if(s[i]>ps[j]&&s[i]<=(ps[j+1])){
mn[i][j][0]=s[i];
go[i][j][0]=l[i];
up[i][j][0]=p[i];
}
else if(s[i]<=ps[j]){
go[i][j][0]=w[i];
up[i][j][0]=s[i];
mn[i][j][0]=1e9;
}
else{
go[i][j][0]=l[i];
up[i][j][0]=p[i];
mn[i][j][0]=1e9;
}
}
for(int st=1;st<lt;st++){
for(int i=0;i<=n;i++){
mn[i][j][st]=min(mn[i][j][st-1],mn[go[i][j][st-1]][j][st-1]-up[i][j][st-1]);
go[i][j][st]=go[go[i][j][st-1]][j][st-1];
up[i][j][st]=min(ps.back(),up[i][j][st-1]+up[go[i][j][st-1]][j][st-1]);
}
}
}
}
ll clever_query(int x,int z){
ll sm=z;
int t=upper_bound(all(ps),sm)-ps.begin()-1;
while(sm<kek.back() && x!=n){
while(sm>=(ps[t+1])) ++t;
for(int j=lt-1;j>=0;j--){
if(mn[x][t][j]>sm && (sm+up[x][t][j])<=kek.back() && (sm+up[x][t][j])<(ps[t+1])){
sm+=up[x][t][j];
x=go[x][t][j];
}
}
if(sm<s[x]){
sm+=p[x];
x=l[x];
}
else{
sm+=s[x];
x=w[x];
}
}
if(x!=n) assert(sm>=kek.back());
sm+=pode[x];
return sm;
}
void init(int n, vec<int> a,vec<int> b,vec<int> c,vec<int> d){
for(int i=0;i<n;i++){
s[i]=a[i];
p[i]=b[i];
w[i]=c[i];
l[i]=d[i];
}
s[n]=0;w[n]=n;l[n]=n;p[n]=0;
::n=n;
for(int i=0;i<n;i++) kek.pb(s[i]);
sort(all(kek));kek.erase(unique(all(kek)),kek.end());
clever_init();
}
long long simulate(int x, int z){
return clever_query(x,z);
}
/*
3 2
13 13 13
4 3 1
2 2 3
1 0 1
0 1
2 3
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
3 ms |
3136 KB |
Output is correct |
4 |
Correct |
198 ms |
71404 KB |
Output is correct |
5 |
Correct |
3 ms |
3132 KB |
Output is correct |
6 |
Correct |
183 ms |
71240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1748 KB |
Output is correct |
2 |
Correct |
1609 ms |
567012 KB |
Output is correct |
3 |
Correct |
1538 ms |
567208 KB |
Output is correct |
4 |
Correct |
1511 ms |
568544 KB |
Output is correct |
5 |
Correct |
1577 ms |
568588 KB |
Output is correct |
6 |
Correct |
1757 ms |
567016 KB |
Output is correct |
7 |
Correct |
1745 ms |
565184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1780 KB |
Output is correct |
2 |
Correct |
212 ms |
72744 KB |
Output is correct |
3 |
Correct |
187 ms |
73020 KB |
Output is correct |
4 |
Correct |
175 ms |
72260 KB |
Output is correct |
5 |
Correct |
176 ms |
72248 KB |
Output is correct |
6 |
Correct |
265 ms |
72400 KB |
Output is correct |
7 |
Correct |
273 ms |
72400 KB |
Output is correct |
8 |
Correct |
178 ms |
72240 KB |
Output is correct |
9 |
Correct |
197 ms |
72136 KB |
Output is correct |
10 |
Correct |
193 ms |
72020 KB |
Output is correct |
11 |
Correct |
374 ms |
72416 KB |
Output is correct |
12 |
Correct |
2578 ms |
72396 KB |
Output is correct |
13 |
Correct |
2462 ms |
72404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1780 KB |
Output is correct |
2 |
Correct |
212 ms |
72744 KB |
Output is correct |
3 |
Correct |
187 ms |
73020 KB |
Output is correct |
4 |
Correct |
175 ms |
72260 KB |
Output is correct |
5 |
Correct |
176 ms |
72248 KB |
Output is correct |
6 |
Correct |
265 ms |
72400 KB |
Output is correct |
7 |
Correct |
273 ms |
72400 KB |
Output is correct |
8 |
Correct |
178 ms |
72240 KB |
Output is correct |
9 |
Correct |
197 ms |
72136 KB |
Output is correct |
10 |
Correct |
193 ms |
72020 KB |
Output is correct |
11 |
Correct |
374 ms |
72416 KB |
Output is correct |
12 |
Correct |
2578 ms |
72396 KB |
Output is correct |
13 |
Correct |
2462 ms |
72404 KB |
Output is correct |
14 |
Correct |
2 ms |
1748 KB |
Output is correct |
15 |
Correct |
231 ms |
72524 KB |
Output is correct |
16 |
Correct |
202 ms |
72728 KB |
Output is correct |
17 |
Correct |
192 ms |
72256 KB |
Output is correct |
18 |
Correct |
231 ms |
72392 KB |
Output is correct |
19 |
Correct |
258 ms |
72404 KB |
Output is correct |
20 |
Correct |
300 ms |
72140 KB |
Output is correct |
21 |
Correct |
266 ms |
72268 KB |
Output is correct |
22 |
Correct |
296 ms |
72244 KB |
Output is correct |
23 |
Correct |
387 ms |
72392 KB |
Output is correct |
24 |
Correct |
534 ms |
72400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1780 KB |
Output is correct |
2 |
Correct |
212 ms |
72744 KB |
Output is correct |
3 |
Correct |
187 ms |
73020 KB |
Output is correct |
4 |
Correct |
175 ms |
72260 KB |
Output is correct |
5 |
Correct |
176 ms |
72248 KB |
Output is correct |
6 |
Correct |
265 ms |
72400 KB |
Output is correct |
7 |
Correct |
273 ms |
72400 KB |
Output is correct |
8 |
Correct |
178 ms |
72240 KB |
Output is correct |
9 |
Correct |
197 ms |
72136 KB |
Output is correct |
10 |
Correct |
193 ms |
72020 KB |
Output is correct |
11 |
Correct |
374 ms |
72416 KB |
Output is correct |
12 |
Correct |
2578 ms |
72396 KB |
Output is correct |
13 |
Correct |
2462 ms |
72404 KB |
Output is correct |
14 |
Correct |
2 ms |
1748 KB |
Output is correct |
15 |
Correct |
231 ms |
72524 KB |
Output is correct |
16 |
Correct |
202 ms |
72728 KB |
Output is correct |
17 |
Correct |
192 ms |
72256 KB |
Output is correct |
18 |
Correct |
231 ms |
72392 KB |
Output is correct |
19 |
Correct |
258 ms |
72404 KB |
Output is correct |
20 |
Correct |
300 ms |
72140 KB |
Output is correct |
21 |
Correct |
266 ms |
72268 KB |
Output is correct |
22 |
Correct |
296 ms |
72244 KB |
Output is correct |
23 |
Correct |
387 ms |
72392 KB |
Output is correct |
24 |
Correct |
534 ms |
72400 KB |
Output is correct |
25 |
Correct |
198 ms |
71612 KB |
Output is correct |
26 |
Correct |
243 ms |
72772 KB |
Output is correct |
27 |
Correct |
209 ms |
72172 KB |
Output is correct |
28 |
Correct |
180 ms |
72248 KB |
Output is correct |
29 |
Correct |
238 ms |
72656 KB |
Output is correct |
30 |
Correct |
259 ms |
72332 KB |
Output is correct |
31 |
Correct |
279 ms |
72140 KB |
Output is correct |
32 |
Correct |
338 ms |
72272 KB |
Output is correct |
33 |
Correct |
539 ms |
72252 KB |
Output is correct |
34 |
Correct |
869 ms |
72244 KB |
Output is correct |
35 |
Correct |
484 ms |
72400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1748 KB |
Output is correct |
2 |
Correct |
1609 ms |
567012 KB |
Output is correct |
3 |
Correct |
1538 ms |
567208 KB |
Output is correct |
4 |
Correct |
1511 ms |
568544 KB |
Output is correct |
5 |
Correct |
1577 ms |
568588 KB |
Output is correct |
6 |
Correct |
1757 ms |
567016 KB |
Output is correct |
7 |
Correct |
1745 ms |
565184 KB |
Output is correct |
8 |
Correct |
3 ms |
1780 KB |
Output is correct |
9 |
Correct |
212 ms |
72744 KB |
Output is correct |
10 |
Correct |
187 ms |
73020 KB |
Output is correct |
11 |
Correct |
175 ms |
72260 KB |
Output is correct |
12 |
Correct |
176 ms |
72248 KB |
Output is correct |
13 |
Correct |
265 ms |
72400 KB |
Output is correct |
14 |
Correct |
273 ms |
72400 KB |
Output is correct |
15 |
Correct |
178 ms |
72240 KB |
Output is correct |
16 |
Correct |
197 ms |
72136 KB |
Output is correct |
17 |
Correct |
193 ms |
72020 KB |
Output is correct |
18 |
Correct |
374 ms |
72416 KB |
Output is correct |
19 |
Correct |
2578 ms |
72396 KB |
Output is correct |
20 |
Correct |
2462 ms |
72404 KB |
Output is correct |
21 |
Correct |
2 ms |
1748 KB |
Output is correct |
22 |
Correct |
231 ms |
72524 KB |
Output is correct |
23 |
Correct |
202 ms |
72728 KB |
Output is correct |
24 |
Correct |
192 ms |
72256 KB |
Output is correct |
25 |
Correct |
231 ms |
72392 KB |
Output is correct |
26 |
Correct |
258 ms |
72404 KB |
Output is correct |
27 |
Correct |
300 ms |
72140 KB |
Output is correct |
28 |
Correct |
266 ms |
72268 KB |
Output is correct |
29 |
Correct |
296 ms |
72244 KB |
Output is correct |
30 |
Correct |
387 ms |
72392 KB |
Output is correct |
31 |
Correct |
534 ms |
72400 KB |
Output is correct |
32 |
Correct |
198 ms |
71612 KB |
Output is correct |
33 |
Correct |
243 ms |
72772 KB |
Output is correct |
34 |
Correct |
209 ms |
72172 KB |
Output is correct |
35 |
Correct |
180 ms |
72248 KB |
Output is correct |
36 |
Correct |
238 ms |
72656 KB |
Output is correct |
37 |
Correct |
259 ms |
72332 KB |
Output is correct |
38 |
Correct |
279 ms |
72140 KB |
Output is correct |
39 |
Correct |
338 ms |
72272 KB |
Output is correct |
40 |
Correct |
539 ms |
72252 KB |
Output is correct |
41 |
Correct |
869 ms |
72244 KB |
Output is correct |
42 |
Correct |
484 ms |
72400 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
2 ms |
1748 KB |
Output is correct |
45 |
Correct |
1951 ms |
571720 KB |
Output is correct |
46 |
Correct |
1581 ms |
567256 KB |
Output is correct |
47 |
Correct |
1536 ms |
567460 KB |
Output is correct |
48 |
Correct |
1523 ms |
569704 KB |
Output is correct |
49 |
Correct |
2053 ms |
571748 KB |
Output is correct |
50 |
Correct |
1658 ms |
569404 KB |
Output is correct |
51 |
Correct |
1557 ms |
569628 KB |
Output is correct |
52 |
Correct |
1665 ms |
567460 KB |
Output is correct |
53 |
Correct |
2404 ms |
568124 KB |
Output is correct |
54 |
Correct |
2136 ms |
569304 KB |
Output is correct |
55 |
Correct |
2676 ms |
568300 KB |
Output is correct |
56 |
Correct |
2484 ms |
569060 KB |
Output is correct |
57 |
Correct |
2654 ms |
569112 KB |
Output is correct |
58 |
Correct |
2638 ms |
568968 KB |
Output is correct |
59 |
Correct |
2729 ms |
569196 KB |
Output is correct |
60 |
Correct |
2916 ms |
568428 KB |
Output is correct |
61 |
Correct |
2823 ms |
568356 KB |
Output is correct |