#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+100;
const int L=23;
const int INF=1e9;
int a[NN];
bool vis[NN];
int seg[4*NN];
int n;
vector<int> g[NN];
vector<int> vec;
int st[NN][L][2];
void build(int p,int s,int e)
{
if(s==e){
seg[p]=a[s];
return;
}
int mid=(s+e)/2;
build(2*p,s,mid);
build(2*p+1,mid+1,e);
seg[p]=max( seg[2*p],seg[2*p+1]);
}
int get(int p,int s,int e,int a, int b)
{
if(a<=s&&e<=b){
return seg[p];
}
if(s>b||e<a){
return 0;
}
int mid=(s+e)/2;
return max(get(2*p,s,mid,a,b),get(2*p+1,mid+1,e,a,b));
}
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];
}
build(1,0,n-1);
for(int i=0;i<n;i++){
if(i!=n-1&&get(1,0,n-1,i,n-1)!=a[i]){
int ans,l=i,r=n-1;
while(l<=r){
int mid=(l+r)/2;
int v=get(1,0,n-1,i+1,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(1,0,n-1,0,i)!=a[i]){
int ans,l=0,r=i;
while(l<=r){
int mid=(l+r)/2;
int v=get(1,0,n-1,mid,i-1);
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 ans=dfs(a[A],a[C]);
if(ans==INF)ans=-1;
return ans;
}
Compilation message
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:52:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
52 | int ans,l=i,r=n-1;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4936 KB |
Output is correct |
2 |
Correct |
5 ms |
4936 KB |
Output is correct |
3 |
Incorrect |
1095 ms |
42616 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 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 |
3 ms |
4936 KB |
Output is correct |
2 |
Correct |
5 ms |
4936 KB |
Output is correct |
3 |
Correct |
4 ms |
4936 KB |
Output is correct |
4 |
Correct |
1353 ms |
26416 KB |
Output is correct |
5 |
Correct |
3757 ms |
51588 KB |
Output is correct |
6 |
Correct |
1085 ms |
12792 KB |
Output is correct |
7 |
Correct |
3387 ms |
51540 KB |
Output is correct |
8 |
Correct |
1455 ms |
21296 KB |
Output is correct |
9 |
Correct |
3640 ms |
51652 KB |
Output is correct |
10 |
Correct |
2522 ms |
51556 KB |
Output is correct |
11 |
Correct |
3826 ms |
51576 KB |
Output is correct |
12 |
Correct |
2508 ms |
51684 KB |
Output is correct |
13 |
Correct |
3420 ms |
51564 KB |
Output is correct |
14 |
Correct |
3628 ms |
51708 KB |
Output is correct |
15 |
Correct |
2266 ms |
51660 KB |
Output is correct |
16 |
Correct |
2522 ms |
51660 KB |
Output is correct |
17 |
Correct |
4 ms |
4892 KB |
Output is correct |
18 |
Correct |
4 ms |
4936 KB |
Output is correct |
19 |
Correct |
8 ms |
4936 KB |
Output is correct |
20 |
Correct |
7 ms |
4936 KB |
Output is correct |
21 |
Correct |
6 ms |
4936 KB |
Output is correct |
22 |
Correct |
9 ms |
4936 KB |
Output is correct |
23 |
Correct |
8 ms |
4936 KB |
Output is correct |
24 |
Correct |
6 ms |
4936 KB |
Output is correct |
25 |
Correct |
5 ms |
4936 KB |
Output is correct |
26 |
Correct |
8 ms |
5164 KB |
Output is correct |
27 |
Correct |
41 ms |
5448 KB |
Output is correct |
28 |
Correct |
45 ms |
5448 KB |
Output is correct |
29 |
Correct |
34 ms |
5448 KB |
Output is correct |
30 |
Correct |
26 ms |
5460 KB |
Output is correct |
31 |
Correct |
24 ms |
5448 KB |
Output is correct |
32 |
Correct |
4 ms |
4936 KB |
Output is correct |
33 |
Correct |
1200 ms |
31836 KB |
Output is correct |
34 |
Correct |
2329 ms |
51548 KB |
Output is correct |
35 |
Correct |
1444 ms |
51648 KB |
Output is correct |
36 |
Correct |
2383 ms |
51608 KB |
Output is correct |
37 |
Correct |
2510 ms |
51544 KB |
Output is correct |
38 |
Correct |
1454 ms |
51724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4936 KB |
Output is correct |
2 |
Correct |
5 ms |
4936 KB |
Output is correct |
3 |
Correct |
4 ms |
4936 KB |
Output is correct |
4 |
Correct |
1353 ms |
26416 KB |
Output is correct |
5 |
Correct |
3757 ms |
51588 KB |
Output is correct |
6 |
Correct |
1085 ms |
12792 KB |
Output is correct |
7 |
Correct |
3387 ms |
51540 KB |
Output is correct |
8 |
Correct |
1455 ms |
21296 KB |
Output is correct |
9 |
Correct |
3640 ms |
51652 KB |
Output is correct |
10 |
Correct |
2522 ms |
51556 KB |
Output is correct |
11 |
Correct |
3826 ms |
51576 KB |
Output is correct |
12 |
Correct |
2508 ms |
51684 KB |
Output is correct |
13 |
Correct |
3420 ms |
51564 KB |
Output is correct |
14 |
Correct |
3628 ms |
51708 KB |
Output is correct |
15 |
Correct |
2266 ms |
51660 KB |
Output is correct |
16 |
Correct |
2522 ms |
51660 KB |
Output is correct |
17 |
Correct |
4 ms |
4892 KB |
Output is correct |
18 |
Correct |
4 ms |
4936 KB |
Output is correct |
19 |
Correct |
8 ms |
4936 KB |
Output is correct |
20 |
Correct |
7 ms |
4936 KB |
Output is correct |
21 |
Correct |
6 ms |
4936 KB |
Output is correct |
22 |
Correct |
9 ms |
4936 KB |
Output is correct |
23 |
Correct |
8 ms |
4936 KB |
Output is correct |
24 |
Correct |
6 ms |
4936 KB |
Output is correct |
25 |
Correct |
5 ms |
4936 KB |
Output is correct |
26 |
Correct |
8 ms |
5164 KB |
Output is correct |
27 |
Correct |
41 ms |
5448 KB |
Output is correct |
28 |
Correct |
45 ms |
5448 KB |
Output is correct |
29 |
Correct |
34 ms |
5448 KB |
Output is correct |
30 |
Correct |
26 ms |
5460 KB |
Output is correct |
31 |
Correct |
24 ms |
5448 KB |
Output is correct |
32 |
Correct |
4 ms |
4936 KB |
Output is correct |
33 |
Correct |
1200 ms |
31836 KB |
Output is correct |
34 |
Correct |
2329 ms |
51548 KB |
Output is correct |
35 |
Correct |
1444 ms |
51648 KB |
Output is correct |
36 |
Correct |
2383 ms |
51608 KB |
Output is correct |
37 |
Correct |
2510 ms |
51544 KB |
Output is correct |
38 |
Correct |
1454 ms |
51724 KB |
Output is correct |
39 |
Correct |
5 ms |
4976 KB |
Output is correct |
40 |
Correct |
4 ms |
4936 KB |
Output is correct |
41 |
Correct |
5 ms |
4936 KB |
Output is correct |
42 |
Correct |
1062 ms |
26292 KB |
Output is correct |
43 |
Correct |
3353 ms |
51540 KB |
Output is correct |
44 |
Correct |
1036 ms |
12864 KB |
Output is correct |
45 |
Correct |
3648 ms |
51660 KB |
Output is correct |
46 |
Correct |
1165 ms |
21292 KB |
Output is correct |
47 |
Correct |
3428 ms |
51576 KB |
Output is correct |
48 |
Correct |
2361 ms |
51788 KB |
Output is correct |
49 |
Correct |
3282 ms |
51644 KB |
Output is correct |
50 |
Correct |
2610 ms |
51644 KB |
Output is correct |
51 |
Correct |
3109 ms |
51652 KB |
Output is correct |
52 |
Correct |
3564 ms |
51736 KB |
Output is correct |
53 |
Correct |
2566 ms |
51752 KB |
Output is correct |
54 |
Correct |
2337 ms |
51560 KB |
Output is correct |
55 |
Correct |
4 ms |
4936 KB |
Output is correct |
56 |
Incorrect |
2410 ms |
51536 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4936 KB |
Output is correct |
2 |
Correct |
5 ms |
4936 KB |
Output is correct |
3 |
Incorrect |
1095 ms |
42616 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |