#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+100;
const int L=18;
const int INF=1e9;
int a[NN],lo[NN];
bool vis[NN];
int seg[4*NN];
int n;
vector<int> g[NN];
vector<int> vec;
int st[NN][L][2];
int stt[NN][L];
void build()
{
lo[1]=0;
for(int i=2;i<=n+1;i++){
lo[i]=lo[i/2]+1;
}
for (int j=1;j<L;j++){
for (int i=0;i+(1 << j)<=n;i++){
stt[i][j]=max(stt[i][j-1],stt[i+(1<<(j-1))][j-1]);
}
}
}
int get(int L,int R)
{
if(R<L)assert(0);
int j = lo[R - L + 1];
int ret=max(stt[L][j], stt[R - (1 << j) + 1][j]);
return ret;
}
void init(int N, std::vector<int> H) {
n=N;
for(int i=0;i<L;i++){
st[n+1][i][0]=n+1;
st[n+1][i][1]=n+1;
}
for(int i=0;i<N;i++){
a[i]=H[i];
stt[i][0]=a[i];
}
build();
for(int i=0;i<n;i++){
if(i!=n-1&&get(i,n-1)!=a[i]){
int ans,l=i+1,r=n-1;
while(l<=r){
int mid=(l+r)/2;
int v=get(i,mid);
if(v>a[i]){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
g[a[i]].push_back(a[ans]);
}
if(i!=0&&get(0,i)!=a[i]){
int ans,l=0,r=i-1;
while(l<=r){
int mid=(l+r)/2;
int v=get(mid,i);
if(v>a[i]){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
g[a[i]].push_back(a[ans]);
}
sort(g[a[i]].begin(),g[a[i]].end());
if(g[a[i]].size()>0){
st[a[i]][0][0]=g[a[i]][0];
}
else{
st[a[i]][0][0]=n+1;
}
if(g[a[i]].size()>1){
st[a[i]][0][1]=g[a[i]][1];
}
else{
st[a[i]][0][1]=n+1;
}
}
for(int j=1;j<L;j++){
for(int i=1;i<=n;i++){
int r=i;
r=st[r][j-1][0];
r=st[r][j-1][0];
st[i][j][0]=r;
r=i;
r=st[r][j-1][1];
r=st[r][j-1][1];
st[i][j][1]=r;
}
}
}
int dfs(int u,int tar)
{
int ret=0;
for(int i=1;i>=0;i--){
for(int j=L-1;j>=0;j--){
int r=st[u][j][i];
if(r<=tar){
ret+=(1<<j);
u=r;
}
}
}
if(u==tar)return ret;
else return INF;
}
int minimum_jumps(int A,int B,int C,int D){
int u=a[B];
int tar=a[C];
if(u>tar)return -1;
int l=A,r=B;
while(l<=r){
int mid=(l+r)/2;
if(get(mid,B)<tar){
r=mid-1;
u=get(mid,B);
}
else{
l=mid+1;
}
}
int ans=dfs(u,tar);
if(ans==INF)ans=-1;
return ans;
}
Compilation message
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:51:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
51 | int ans,l=i+1,r=n-1;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4936 KB |
Output is correct |
2 |
Correct |
4 ms |
4936 KB |
Output is correct |
3 |
Correct |
257 ms |
46036 KB |
Output is correct |
4 |
Correct |
1531 ms |
56660 KB |
Output is correct |
5 |
Correct |
1165 ms |
31020 KB |
Output is correct |
6 |
Correct |
1656 ms |
56660 KB |
Output is correct |
7 |
Correct |
1290 ms |
40196 KB |
Output is correct |
8 |
Correct |
1458 ms |
56572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4936 KB |
Output is correct |
2 |
Correct |
4 ms |
4936 KB |
Output is correct |
3 |
Correct |
4 ms |
4936 KB |
Output is correct |
4 |
Correct |
412 ms |
28612 KB |
Output is correct |
5 |
Correct |
1523 ms |
56740 KB |
Output is correct |
6 |
Correct |
703 ms |
13504 KB |
Output is correct |
7 |
Correct |
1320 ms |
56552 KB |
Output is correct |
8 |
Correct |
679 ms |
22924 KB |
Output is correct |
9 |
Correct |
1505 ms |
56640 KB |
Output is correct |
10 |
Correct |
1421 ms |
56560 KB |
Output is correct |
11 |
Correct |
1485 ms |
56684 KB |
Output is correct |
12 |
Correct |
1216 ms |
56640 KB |
Output is correct |
13 |
Correct |
1468 ms |
56828 KB |
Output is correct |
14 |
Correct |
1426 ms |
56704 KB |
Output is correct |
15 |
Correct |
1202 ms |
56588 KB |
Output is correct |
16 |
Correct |
1135 ms |
56572 KB |
Output is correct |
17 |
Correct |
4 ms |
4936 KB |
Output is correct |
18 |
Correct |
4 ms |
4936 KB |
Output is correct |
19 |
Correct |
5 ms |
4936 KB |
Output is correct |
20 |
Correct |
5 ms |
5064 KB |
Output is correct |
21 |
Correct |
5 ms |
5064 KB |
Output is correct |
22 |
Correct |
6 ms |
5064 KB |
Output is correct |
23 |
Correct |
7 ms |
5064 KB |
Output is correct |
24 |
Correct |
7 ms |
5064 KB |
Output is correct |
25 |
Correct |
5 ms |
5064 KB |
Output is correct |
26 |
Correct |
5 ms |
5192 KB |
Output is correct |
27 |
Correct |
21 ms |
5448 KB |
Output is correct |
28 |
Correct |
34 ms |
5448 KB |
Output is correct |
29 |
Correct |
15 ms |
5448 KB |
Output is correct |
30 |
Correct |
25 ms |
5448 KB |
Output is correct |
31 |
Correct |
25 ms |
5448 KB |
Output is correct |
32 |
Correct |
4 ms |
4936 KB |
Output is correct |
33 |
Correct |
176 ms |
34804 KB |
Output is correct |
34 |
Correct |
314 ms |
56828 KB |
Output is correct |
35 |
Correct |
175 ms |
56712 KB |
Output is correct |
36 |
Correct |
274 ms |
56684 KB |
Output is correct |
37 |
Correct |
249 ms |
56556 KB |
Output is correct |
38 |
Correct |
179 ms |
56700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4936 KB |
Output is correct |
2 |
Correct |
4 ms |
4936 KB |
Output is correct |
3 |
Correct |
4 ms |
4936 KB |
Output is correct |
4 |
Correct |
412 ms |
28612 KB |
Output is correct |
5 |
Correct |
1523 ms |
56740 KB |
Output is correct |
6 |
Correct |
703 ms |
13504 KB |
Output is correct |
7 |
Correct |
1320 ms |
56552 KB |
Output is correct |
8 |
Correct |
679 ms |
22924 KB |
Output is correct |
9 |
Correct |
1505 ms |
56640 KB |
Output is correct |
10 |
Correct |
1421 ms |
56560 KB |
Output is correct |
11 |
Correct |
1485 ms |
56684 KB |
Output is correct |
12 |
Correct |
1216 ms |
56640 KB |
Output is correct |
13 |
Correct |
1468 ms |
56828 KB |
Output is correct |
14 |
Correct |
1426 ms |
56704 KB |
Output is correct |
15 |
Correct |
1202 ms |
56588 KB |
Output is correct |
16 |
Correct |
1135 ms |
56572 KB |
Output is correct |
17 |
Correct |
4 ms |
4936 KB |
Output is correct |
18 |
Correct |
4 ms |
4936 KB |
Output is correct |
19 |
Correct |
5 ms |
4936 KB |
Output is correct |
20 |
Correct |
5 ms |
5064 KB |
Output is correct |
21 |
Correct |
5 ms |
5064 KB |
Output is correct |
22 |
Correct |
6 ms |
5064 KB |
Output is correct |
23 |
Correct |
7 ms |
5064 KB |
Output is correct |
24 |
Correct |
7 ms |
5064 KB |
Output is correct |
25 |
Correct |
5 ms |
5064 KB |
Output is correct |
26 |
Correct |
5 ms |
5192 KB |
Output is correct |
27 |
Correct |
21 ms |
5448 KB |
Output is correct |
28 |
Correct |
34 ms |
5448 KB |
Output is correct |
29 |
Correct |
15 ms |
5448 KB |
Output is correct |
30 |
Correct |
25 ms |
5448 KB |
Output is correct |
31 |
Correct |
25 ms |
5448 KB |
Output is correct |
32 |
Correct |
4 ms |
4936 KB |
Output is correct |
33 |
Correct |
176 ms |
34804 KB |
Output is correct |
34 |
Correct |
314 ms |
56828 KB |
Output is correct |
35 |
Correct |
175 ms |
56712 KB |
Output is correct |
36 |
Correct |
274 ms |
56684 KB |
Output is correct |
37 |
Correct |
249 ms |
56556 KB |
Output is correct |
38 |
Correct |
179 ms |
56700 KB |
Output is correct |
39 |
Correct |
4 ms |
4936 KB |
Output is correct |
40 |
Correct |
4 ms |
4936 KB |
Output is correct |
41 |
Correct |
4 ms |
4936 KB |
Output is correct |
42 |
Correct |
386 ms |
28540 KB |
Output is correct |
43 |
Correct |
1116 ms |
56640 KB |
Output is correct |
44 |
Correct |
851 ms |
13536 KB |
Output is correct |
45 |
Correct |
1482 ms |
56660 KB |
Output is correct |
46 |
Correct |
585 ms |
22804 KB |
Output is correct |
47 |
Correct |
1281 ms |
56564 KB |
Output is correct |
48 |
Correct |
1190 ms |
56644 KB |
Output is correct |
49 |
Correct |
1322 ms |
56588 KB |
Output is correct |
50 |
Correct |
1387 ms |
56688 KB |
Output is correct |
51 |
Correct |
1167 ms |
56632 KB |
Output is correct |
52 |
Correct |
1586 ms |
56572 KB |
Output is correct |
53 |
Correct |
1281 ms |
56712 KB |
Output is correct |
54 |
Correct |
1022 ms |
56568 KB |
Output is correct |
55 |
Correct |
4 ms |
4936 KB |
Output is correct |
56 |
Correct |
351 ms |
56500 KB |
Output is correct |
57 |
Correct |
1278 ms |
56560 KB |
Output is correct |
58 |
Correct |
542 ms |
14072 KB |
Output is correct |
59 |
Correct |
1620 ms |
56768 KB |
Output is correct |
60 |
Correct |
780 ms |
23232 KB |
Output is correct |
61 |
Correct |
1115 ms |
56588 KB |
Output is correct |
62 |
Correct |
1429 ms |
56552 KB |
Output is correct |
63 |
Correct |
1223 ms |
56660 KB |
Output is correct |
64 |
Correct |
1546 ms |
56584 KB |
Output is correct |
65 |
Correct |
1367 ms |
56568 KB |
Output is correct |
66 |
Correct |
1605 ms |
56656 KB |
Output is correct |
67 |
Correct |
1253 ms |
56640 KB |
Output is correct |
68 |
Correct |
1008 ms |
56640 KB |
Output is correct |
69 |
Correct |
4 ms |
4936 KB |
Output is correct |
70 |
Correct |
4 ms |
4936 KB |
Output is correct |
71 |
Correct |
8 ms |
5064 KB |
Output is correct |
72 |
Correct |
7 ms |
5064 KB |
Output is correct |
73 |
Correct |
6 ms |
5064 KB |
Output is correct |
74 |
Correct |
6 ms |
5064 KB |
Output is correct |
75 |
Correct |
7 ms |
5064 KB |
Output is correct |
76 |
Correct |
5 ms |
4904 KB |
Output is correct |
77 |
Correct |
4 ms |
4936 KB |
Output is correct |
78 |
Correct |
6 ms |
4936 KB |
Output is correct |
79 |
Correct |
8 ms |
5064 KB |
Output is correct |
80 |
Correct |
8 ms |
5064 KB |
Output is correct |
81 |
Correct |
7 ms |
5064 KB |
Output is correct |
82 |
Correct |
7 ms |
5064 KB |
Output is correct |
83 |
Correct |
8 ms |
5064 KB |
Output is correct |
84 |
Correct |
4 ms |
5064 KB |
Output is correct |
85 |
Correct |
5 ms |
5064 KB |
Output is correct |
86 |
Correct |
33 ms |
5448 KB |
Output is correct |
87 |
Correct |
35 ms |
5448 KB |
Output is correct |
88 |
Correct |
36 ms |
5448 KB |
Output is correct |
89 |
Correct |
36 ms |
5448 KB |
Output is correct |
90 |
Correct |
23 ms |
5448 KB |
Output is correct |
91 |
Correct |
5 ms |
5064 KB |
Output is correct |
92 |
Correct |
5 ms |
5192 KB |
Output is correct |
93 |
Correct |
34 ms |
5448 KB |
Output is correct |
94 |
Correct |
39 ms |
5448 KB |
Output is correct |
95 |
Correct |
36 ms |
5448 KB |
Output is correct |
96 |
Correct |
35 ms |
5448 KB |
Output is correct |
97 |
Correct |
21 ms |
5448 KB |
Output is correct |
98 |
Correct |
4 ms |
4936 KB |
Output is correct |
99 |
Correct |
324 ms |
56688 KB |
Output is correct |
100 |
Correct |
267 ms |
56604 KB |
Output is correct |
101 |
Correct |
178 ms |
56648 KB |
Output is correct |
102 |
Correct |
256 ms |
56640 KB |
Output is correct |
103 |
Correct |
272 ms |
56552 KB |
Output is correct |
104 |
Correct |
190 ms |
56776 KB |
Output is correct |
105 |
Correct |
4 ms |
4936 KB |
Output is correct |
106 |
Correct |
177 ms |
34880 KB |
Output is correct |
107 |
Correct |
267 ms |
56668 KB |
Output is correct |
108 |
Correct |
167 ms |
56572 KB |
Output is correct |
109 |
Correct |
314 ms |
56640 KB |
Output is correct |
110 |
Correct |
253 ms |
56560 KB |
Output is correct |
111 |
Correct |
202 ms |
56568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4936 KB |
Output is correct |
2 |
Correct |
4 ms |
4936 KB |
Output is correct |
3 |
Correct |
257 ms |
46036 KB |
Output is correct |
4 |
Correct |
1531 ms |
56660 KB |
Output is correct |
5 |
Correct |
1165 ms |
31020 KB |
Output is correct |
6 |
Correct |
1656 ms |
56660 KB |
Output is correct |
7 |
Correct |
1290 ms |
40196 KB |
Output is correct |
8 |
Correct |
1458 ms |
56572 KB |
Output is correct |
9 |
Incorrect |
4 ms |
4936 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |