#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAX_N=2e5+10;
const int MAX_P=MAX_N*4;
int st[MAX_P];
int val[MAX_N];
int n;
vector<vi> lo,hi;
void init_tr(int node,int a,int b){
if(a==b){
st[node]=val[a];
return;
}
int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
init_tr(le,a,mid);
init_tr(ri,mid+1,b);
st[node]=max(st[le],st[ri]);
}
int query(int node,int a,int b,int l,int r){
if(b<l || a>r) return 0;
if(l<=a && r>=b) return st[node];
int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
return max(query(le,a,mid,l,r),query(ri,mid+1,b,l,r));
}
int izquier(int x){
int q=query(0,0,n-1,0,x);
if(q==val[x]) return -1;
int l=0,r=x;
while(r-l>1){
int mid=(l+r)/2;
q=query(0,0,n-1,mid,r);
if(q>val[x])
l=mid;
else r=mid;
}
return l;
}
int derecha(int x){
int q=query(0,0,n-1,x,n-1);
if(q==val[x]) return -1;
int l=x,r=n-1;
while(r-l>1){
int mid=(l+r)/2;
q=query(0,0,n-1,l,mid);
if(q>val[x]) r=mid;
else l=mid;
}
return r;
}
int sh[MAX_N][32];
int sl[MAX_N][32];
bool vis[MAX_N];
void low_edge(int u,int p,int he){
if(he>=1){
sl[u][0]=p;
for(int i=1;i<30;i++){
if((1<<i)>he) break;
sl[u][i]=sl[sl[u][i-1]][i-1];
}
}
vis[u]=1;
for(auto &v:lo[u]){
if(!vis[v] && v!=p){
low_edge(v,u,he+1);
}
}
}
void high_edge(int u,int p,int he){
if(he>=1){
sh[u][0]=p;
for(int i=1;i<30;i++){
if((1<<i)>he) break;
sh[u][i]=sh[sh[u][i-1]][i-1];
}
}
vis[u]=1;
for(auto &v:hi[u]){
if(!vis[v] && v!=p){
high_edge(v,u,he+1);
}
}
}
int ih[MAX_N],il[MAX_N];
void init(int N, std::vector<int> H) {
for(int i=0;i<N;i++) val[i]=H[i];
hi.resize(N+1);
lo.resize(N+1);
n=N;
memset(ih,0,sizeof ih);
memset(il,0,sizeof il);
init_tr(0,0,n-1);
for(int i=0;i<n;i++){
int l=izquier(i);
int r=derecha(i);
if(r!=-1 && l!=-1){
if(val[r]>val[l]){
hi[r].push_back(i);
lo[l].push_back(i);
}
else{
hi[l].push_back(i);
lo[r].push_back(i);
}
ih[i]++; il[i]++;
}
else{
if(l!=-1) lo[l].push_back(i);
if(r!=-1) lo[r].push_back(i);
if(l!=-1 || r!=-1) il[i]++;
}
}
memset(vis,0,sizeof vis);
memset(sl,-1,sizeof sl);
memset(sh,-1,sizeof sh);
for(int i=n-1;i>=0;i--){
if(!il[i]) low_edge(i,i,0);
}
memset(vis,0,sizeof vis);
for(int i=n-1;i>=0;i--){
if(!ih[i]) high_edge(i,i,0);
}
}
int jumps(int A,int C){
int res=0;
for(int i=29;i>=0;i--){
if(sh[A][i]!=-1 && val[sh[A][i]]<val[C]){
A=sh[A][i];
res+=(1<<i);
}
}
if(val[sh[A][0]]==val[C]) return res+1;
for(int i=29;i>=0;i--){
if(sl[A][i]!=-1 && val[sl[A][i]]<val[C]){
A=sl[A][i];
res+=(1<<i);
}
}
if(val[sl[A][0]]==val[C]) return res+1;
return -1;
}
int encontrar(int q,int l,int r){
if(query(0,0,n-1,l,l)==q) return l;
while(r-l>1){
int mid=(l+r)/2;
if(query(0,0,n-1,l,mid)>=q) r=mid;
else l=mid;
}
return r;
}
int partir(int l,int r,int q){
if(l>r) return r;
int id=encontrar(query(0,0,n-1,l,r),l,r);
if(val[id]>q) return partir(id+1,r,q);
return id;
}
int minimum_jumps(int A, int B, int C, int D) {
if(query(0,0,n-1,A,B)<=val[C]){
A=encontrar(query(0,0,n-1,A,B),A,B);
return jumps(A,C);
}
else{
A=partir(A,B,val[C]);
return jumps(A,C);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
52128 KB |
Output is correct |
2 |
Correct |
21 ms |
52132 KB |
Output is correct |
3 |
Correct |
757 ms |
78552 KB |
Output is correct |
4 |
Correct |
2233 ms |
84660 KB |
Output is correct |
5 |
Correct |
1665 ms |
68528 KB |
Output is correct |
6 |
Correct |
2328 ms |
84748 KB |
Output is correct |
7 |
Correct |
1498 ms |
75040 KB |
Output is correct |
8 |
Correct |
2224 ms |
84608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
52040 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
52040 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
52084 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
52044 KB |
Output is correct |
2 |
Correct |
23 ms |
52040 KB |
Output is correct |
3 |
Correct |
22 ms |
52040 KB |
Output is correct |
4 |
Correct |
815 ms |
61588 KB |
Output is correct |
5 |
Correct |
2457 ms |
72700 KB |
Output is correct |
6 |
Correct |
1031 ms |
55604 KB |
Output is correct |
7 |
Correct |
2583 ms |
72624 KB |
Output is correct |
8 |
Correct |
1071 ms |
59532 KB |
Output is correct |
9 |
Correct |
2408 ms |
72644 KB |
Output is correct |
10 |
Correct |
1941 ms |
84732 KB |
Output is correct |
11 |
Correct |
2383 ms |
84492 KB |
Output is correct |
12 |
Correct |
2004 ms |
83244 KB |
Output is correct |
13 |
Correct |
2344 ms |
72768 KB |
Output is correct |
14 |
Correct |
2461 ms |
86808 KB |
Output is correct |
15 |
Correct |
1599 ms |
84880 KB |
Output is correct |
16 |
Correct |
1809 ms |
84792 KB |
Output is correct |
17 |
Correct |
22 ms |
52168 KB |
Output is correct |
18 |
Correct |
22 ms |
52040 KB |
Output is correct |
19 |
Correct |
24 ms |
52040 KB |
Output is correct |
20 |
Correct |
24 ms |
52168 KB |
Output is correct |
21 |
Correct |
21 ms |
52160 KB |
Output is correct |
22 |
Correct |
22 ms |
52168 KB |
Output is correct |
23 |
Correct |
22 ms |
52164 KB |
Output is correct |
24 |
Correct |
23 ms |
52088 KB |
Output is correct |
25 |
Correct |
21 ms |
52156 KB |
Output is correct |
26 |
Correct |
22 ms |
52168 KB |
Output is correct |
27 |
Correct |
50 ms |
52264 KB |
Output is correct |
28 |
Correct |
45 ms |
52424 KB |
Output is correct |
29 |
Correct |
47 ms |
52288 KB |
Output is correct |
30 |
Correct |
44 ms |
52376 KB |
Output is correct |
31 |
Correct |
45 ms |
52416 KB |
Output is correct |
32 |
Correct |
21 ms |
52128 KB |
Output is correct |
33 |
Correct |
749 ms |
63860 KB |
Output is correct |
34 |
Correct |
1387 ms |
72768 KB |
Output is correct |
35 |
Correct |
882 ms |
82964 KB |
Output is correct |
36 |
Correct |
1341 ms |
72632 KB |
Output is correct |
37 |
Correct |
1398 ms |
86720 KB |
Output is correct |
38 |
Correct |
872 ms |
84888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
52044 KB |
Output is correct |
2 |
Correct |
23 ms |
52040 KB |
Output is correct |
3 |
Correct |
22 ms |
52040 KB |
Output is correct |
4 |
Correct |
815 ms |
61588 KB |
Output is correct |
5 |
Correct |
2457 ms |
72700 KB |
Output is correct |
6 |
Correct |
1031 ms |
55604 KB |
Output is correct |
7 |
Correct |
2583 ms |
72624 KB |
Output is correct |
8 |
Correct |
1071 ms |
59532 KB |
Output is correct |
9 |
Correct |
2408 ms |
72644 KB |
Output is correct |
10 |
Correct |
1941 ms |
84732 KB |
Output is correct |
11 |
Correct |
2383 ms |
84492 KB |
Output is correct |
12 |
Correct |
2004 ms |
83244 KB |
Output is correct |
13 |
Correct |
2344 ms |
72768 KB |
Output is correct |
14 |
Correct |
2461 ms |
86808 KB |
Output is correct |
15 |
Correct |
1599 ms |
84880 KB |
Output is correct |
16 |
Correct |
1809 ms |
84792 KB |
Output is correct |
17 |
Correct |
22 ms |
52168 KB |
Output is correct |
18 |
Correct |
22 ms |
52040 KB |
Output is correct |
19 |
Correct |
24 ms |
52040 KB |
Output is correct |
20 |
Correct |
24 ms |
52168 KB |
Output is correct |
21 |
Correct |
21 ms |
52160 KB |
Output is correct |
22 |
Correct |
22 ms |
52168 KB |
Output is correct |
23 |
Correct |
22 ms |
52164 KB |
Output is correct |
24 |
Correct |
23 ms |
52088 KB |
Output is correct |
25 |
Correct |
21 ms |
52156 KB |
Output is correct |
26 |
Correct |
22 ms |
52168 KB |
Output is correct |
27 |
Correct |
50 ms |
52264 KB |
Output is correct |
28 |
Correct |
45 ms |
52424 KB |
Output is correct |
29 |
Correct |
47 ms |
52288 KB |
Output is correct |
30 |
Correct |
44 ms |
52376 KB |
Output is correct |
31 |
Correct |
45 ms |
52416 KB |
Output is correct |
32 |
Correct |
21 ms |
52128 KB |
Output is correct |
33 |
Correct |
749 ms |
63860 KB |
Output is correct |
34 |
Correct |
1387 ms |
72768 KB |
Output is correct |
35 |
Correct |
882 ms |
82964 KB |
Output is correct |
36 |
Correct |
1341 ms |
72632 KB |
Output is correct |
37 |
Correct |
1398 ms |
86720 KB |
Output is correct |
38 |
Correct |
872 ms |
84888 KB |
Output is correct |
39 |
Correct |
20 ms |
52040 KB |
Output is correct |
40 |
Correct |
20 ms |
52068 KB |
Output is correct |
41 |
Correct |
19 ms |
52076 KB |
Output is correct |
42 |
Correct |
764 ms |
61764 KB |
Output is correct |
43 |
Correct |
2104 ms |
72600 KB |
Output is correct |
44 |
Correct |
882 ms |
55616 KB |
Output is correct |
45 |
Correct |
2245 ms |
72668 KB |
Output is correct |
46 |
Correct |
1051 ms |
59448 KB |
Output is correct |
47 |
Correct |
2360 ms |
72664 KB |
Output is correct |
48 |
Correct |
1681 ms |
84756 KB |
Output is correct |
49 |
Correct |
2155 ms |
84368 KB |
Output is correct |
50 |
Correct |
1699 ms |
83052 KB |
Output is correct |
51 |
Correct |
2189 ms |
72840 KB |
Output is correct |
52 |
Correct |
2467 ms |
86884 KB |
Output is correct |
53 |
Correct |
1844 ms |
84904 KB |
Output is correct |
54 |
Correct |
1605 ms |
84752 KB |
Output is correct |
55 |
Correct |
25 ms |
52116 KB |
Output is correct |
56 |
Correct |
1733 ms |
72588 KB |
Output is correct |
57 |
Execution timed out |
4017 ms |
72568 KB |
Time limit exceeded |
58 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
52128 KB |
Output is correct |
2 |
Correct |
21 ms |
52132 KB |
Output is correct |
3 |
Correct |
757 ms |
78552 KB |
Output is correct |
4 |
Correct |
2233 ms |
84660 KB |
Output is correct |
5 |
Correct |
1665 ms |
68528 KB |
Output is correct |
6 |
Correct |
2328 ms |
84748 KB |
Output is correct |
7 |
Correct |
1498 ms |
75040 KB |
Output is correct |
8 |
Correct |
2224 ms |
84608 KB |
Output is correct |
9 |
Incorrect |
22 ms |
52040 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |