#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){
int rr=r;
while(r-l>1){
int mid=(l+r)/2;
if(query(0,0,n-1,mid,r)<q) r=mid;
else l=mid;
}
return encontrar(query(0,0,n-1,r,rr),r,rr);
}
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 |
20 ms |
52120 KB |
Output is correct |
2 |
Correct |
25 ms |
52120 KB |
Output is correct |
3 |
Correct |
786 ms |
78512 KB |
Output is correct |
4 |
Correct |
2433 ms |
84732 KB |
Output is correct |
5 |
Correct |
1760 ms |
68444 KB |
Output is correct |
6 |
Correct |
2449 ms |
84680 KB |
Output is correct |
7 |
Correct |
1507 ms |
75032 KB |
Output is correct |
8 |
Correct |
2318 ms |
84716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
52088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
52088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
52112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
52140 KB |
Output is correct |
2 |
Correct |
21 ms |
52156 KB |
Output is correct |
3 |
Correct |
22 ms |
52040 KB |
Output is correct |
4 |
Correct |
916 ms |
61540 KB |
Output is correct |
5 |
Correct |
2147 ms |
72692 KB |
Output is correct |
6 |
Correct |
897 ms |
55708 KB |
Output is correct |
7 |
Correct |
2368 ms |
72792 KB |
Output is correct |
8 |
Correct |
1054 ms |
59584 KB |
Output is correct |
9 |
Correct |
2191 ms |
72680 KB |
Output is correct |
10 |
Correct |
1825 ms |
84680 KB |
Output is correct |
11 |
Correct |
2302 ms |
84456 KB |
Output is correct |
12 |
Correct |
1870 ms |
83128 KB |
Output is correct |
13 |
Correct |
1930 ms |
72632 KB |
Output is correct |
14 |
Correct |
2335 ms |
86812 KB |
Output is correct |
15 |
Correct |
1658 ms |
84844 KB |
Output is correct |
16 |
Correct |
1731 ms |
84792 KB |
Output is correct |
17 |
Correct |
25 ms |
52072 KB |
Output is correct |
18 |
Correct |
22 ms |
52032 KB |
Output is correct |
19 |
Correct |
22 ms |
52068 KB |
Output is correct |
20 |
Correct |
24 ms |
52136 KB |
Output is correct |
21 |
Correct |
23 ms |
52100 KB |
Output is correct |
22 |
Correct |
22 ms |
52064 KB |
Output is correct |
23 |
Correct |
23 ms |
52144 KB |
Output is correct |
24 |
Correct |
23 ms |
52096 KB |
Output is correct |
25 |
Correct |
24 ms |
52168 KB |
Output is correct |
26 |
Correct |
25 ms |
52168 KB |
Output is correct |
27 |
Correct |
47 ms |
52296 KB |
Output is correct |
28 |
Correct |
48 ms |
52424 KB |
Output is correct |
29 |
Correct |
45 ms |
52272 KB |
Output is correct |
30 |
Correct |
42 ms |
52424 KB |
Output is correct |
31 |
Correct |
34 ms |
52424 KB |
Output is correct |
32 |
Correct |
21 ms |
52040 KB |
Output is correct |
33 |
Correct |
730 ms |
63784 KB |
Output is correct |
34 |
Correct |
1351 ms |
72788 KB |
Output is correct |
35 |
Correct |
824 ms |
82860 KB |
Output is correct |
36 |
Correct |
1366 ms |
72852 KB |
Output is correct |
37 |
Correct |
1385 ms |
86748 KB |
Output is correct |
38 |
Correct |
872 ms |
84936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
52140 KB |
Output is correct |
2 |
Correct |
21 ms |
52156 KB |
Output is correct |
3 |
Correct |
22 ms |
52040 KB |
Output is correct |
4 |
Correct |
916 ms |
61540 KB |
Output is correct |
5 |
Correct |
2147 ms |
72692 KB |
Output is correct |
6 |
Correct |
897 ms |
55708 KB |
Output is correct |
7 |
Correct |
2368 ms |
72792 KB |
Output is correct |
8 |
Correct |
1054 ms |
59584 KB |
Output is correct |
9 |
Correct |
2191 ms |
72680 KB |
Output is correct |
10 |
Correct |
1825 ms |
84680 KB |
Output is correct |
11 |
Correct |
2302 ms |
84456 KB |
Output is correct |
12 |
Correct |
1870 ms |
83128 KB |
Output is correct |
13 |
Correct |
1930 ms |
72632 KB |
Output is correct |
14 |
Correct |
2335 ms |
86812 KB |
Output is correct |
15 |
Correct |
1658 ms |
84844 KB |
Output is correct |
16 |
Correct |
1731 ms |
84792 KB |
Output is correct |
17 |
Correct |
25 ms |
52072 KB |
Output is correct |
18 |
Correct |
22 ms |
52032 KB |
Output is correct |
19 |
Correct |
22 ms |
52068 KB |
Output is correct |
20 |
Correct |
24 ms |
52136 KB |
Output is correct |
21 |
Correct |
23 ms |
52100 KB |
Output is correct |
22 |
Correct |
22 ms |
52064 KB |
Output is correct |
23 |
Correct |
23 ms |
52144 KB |
Output is correct |
24 |
Correct |
23 ms |
52096 KB |
Output is correct |
25 |
Correct |
24 ms |
52168 KB |
Output is correct |
26 |
Correct |
25 ms |
52168 KB |
Output is correct |
27 |
Correct |
47 ms |
52296 KB |
Output is correct |
28 |
Correct |
48 ms |
52424 KB |
Output is correct |
29 |
Correct |
45 ms |
52272 KB |
Output is correct |
30 |
Correct |
42 ms |
52424 KB |
Output is correct |
31 |
Correct |
34 ms |
52424 KB |
Output is correct |
32 |
Correct |
21 ms |
52040 KB |
Output is correct |
33 |
Correct |
730 ms |
63784 KB |
Output is correct |
34 |
Correct |
1351 ms |
72788 KB |
Output is correct |
35 |
Correct |
824 ms |
82860 KB |
Output is correct |
36 |
Correct |
1366 ms |
72852 KB |
Output is correct |
37 |
Correct |
1385 ms |
86748 KB |
Output is correct |
38 |
Correct |
872 ms |
84936 KB |
Output is correct |
39 |
Correct |
20 ms |
52040 KB |
Output is correct |
40 |
Correct |
21 ms |
52088 KB |
Output is correct |
41 |
Correct |
21 ms |
52040 KB |
Output is correct |
42 |
Correct |
769 ms |
61660 KB |
Output is correct |
43 |
Correct |
2298 ms |
72720 KB |
Output is correct |
44 |
Correct |
893 ms |
55768 KB |
Output is correct |
45 |
Correct |
2342 ms |
72724 KB |
Output is correct |
46 |
Correct |
947 ms |
59620 KB |
Output is correct |
47 |
Correct |
1983 ms |
72784 KB |
Output is correct |
48 |
Correct |
1662 ms |
84700 KB |
Output is correct |
49 |
Correct |
2080 ms |
84408 KB |
Output is correct |
50 |
Correct |
1925 ms |
83132 KB |
Output is correct |
51 |
Correct |
2364 ms |
72712 KB |
Output is correct |
52 |
Correct |
2462 ms |
86812 KB |
Output is correct |
53 |
Correct |
1749 ms |
84924 KB |
Output is correct |
54 |
Correct |
1788 ms |
84772 KB |
Output is correct |
55 |
Correct |
21 ms |
52040 KB |
Output is correct |
56 |
Correct |
1419 ms |
72768 KB |
Output is correct |
57 |
Correct |
2519 ms |
72788 KB |
Output is correct |
58 |
Correct |
664 ms |
55872 KB |
Output is correct |
59 |
Correct |
2539 ms |
72848 KB |
Output is correct |
60 |
Correct |
757 ms |
59680 KB |
Output is correct |
61 |
Correct |
2599 ms |
72724 KB |
Output is correct |
62 |
Correct |
1787 ms |
84636 KB |
Output is correct |
63 |
Correct |
2660 ms |
82144 KB |
Output is correct |
64 |
Correct |
2411 ms |
80544 KB |
Output is correct |
65 |
Correct |
2579 ms |
72748 KB |
Output is correct |
66 |
Correct |
2494 ms |
86892 KB |
Output is correct |
67 |
Correct |
2205 ms |
85200 KB |
Output is correct |
68 |
Correct |
2113 ms |
84760 KB |
Output is correct |
69 |
Correct |
20 ms |
52032 KB |
Output is correct |
70 |
Correct |
20 ms |
52044 KB |
Output is correct |
71 |
Correct |
23 ms |
52136 KB |
Output is correct |
72 |
Correct |
21 ms |
52124 KB |
Output is correct |
73 |
Correct |
25 ms |
52100 KB |
Output is correct |
74 |
Correct |
23 ms |
52168 KB |
Output is correct |
75 |
Correct |
23 ms |
52168 KB |
Output is correct |
76 |
Correct |
20 ms |
52084 KB |
Output is correct |
77 |
Correct |
21 ms |
52040 KB |
Output is correct |
78 |
Correct |
23 ms |
52040 KB |
Output is correct |
79 |
Correct |
26 ms |
52108 KB |
Output is correct |
80 |
Correct |
25 ms |
52180 KB |
Output is correct |
81 |
Correct |
24 ms |
52044 KB |
Output is correct |
82 |
Correct |
22 ms |
52164 KB |
Output is correct |
83 |
Correct |
23 ms |
52168 KB |
Output is correct |
84 |
Correct |
22 ms |
52164 KB |
Output is correct |
85 |
Correct |
27 ms |
52148 KB |
Output is correct |
86 |
Correct |
43 ms |
52256 KB |
Output is correct |
87 |
Correct |
49 ms |
52424 KB |
Output is correct |
88 |
Correct |
51 ms |
52312 KB |
Output is correct |
89 |
Correct |
46 ms |
52424 KB |
Output is correct |
90 |
Correct |
51 ms |
52424 KB |
Output is correct |
91 |
Correct |
22 ms |
52160 KB |
Output is correct |
92 |
Correct |
22 ms |
52168 KB |
Output is correct |
93 |
Correct |
45 ms |
52236 KB |
Output is correct |
94 |
Correct |
50 ms |
52368 KB |
Output is correct |
95 |
Correct |
44 ms |
52304 KB |
Output is correct |
96 |
Correct |
48 ms |
52472 KB |
Output is correct |
97 |
Correct |
46 ms |
52376 KB |
Output is correct |
98 |
Correct |
21 ms |
52072 KB |
Output is correct |
99 |
Correct |
1353 ms |
72696 KB |
Output is correct |
100 |
Correct |
1343 ms |
72624 KB |
Output is correct |
101 |
Correct |
863 ms |
81968 KB |
Output is correct |
102 |
Correct |
1354 ms |
72656 KB |
Output is correct |
103 |
Correct |
1374 ms |
86724 KB |
Output is correct |
104 |
Correct |
818 ms |
84872 KB |
Output is correct |
105 |
Correct |
21 ms |
52040 KB |
Output is correct |
106 |
Correct |
718 ms |
63956 KB |
Output is correct |
107 |
Correct |
1331 ms |
72808 KB |
Output is correct |
108 |
Correct |
812 ms |
82880 KB |
Output is correct |
109 |
Correct |
1335 ms |
72772 KB |
Output is correct |
110 |
Correct |
1362 ms |
86856 KB |
Output is correct |
111 |
Correct |
862 ms |
84936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
52120 KB |
Output is correct |
2 |
Correct |
25 ms |
52120 KB |
Output is correct |
3 |
Correct |
786 ms |
78512 KB |
Output is correct |
4 |
Correct |
2433 ms |
84732 KB |
Output is correct |
5 |
Correct |
1760 ms |
68444 KB |
Output is correct |
6 |
Correct |
2449 ms |
84680 KB |
Output is correct |
7 |
Correct |
1507 ms |
75032 KB |
Output is correct |
8 |
Correct |
2318 ms |
84716 KB |
Output is correct |
9 |
Incorrect |
24 ms |
52088 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |