#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 200005
int t[4*N],arr[N],nxt[20][N],n;
void cre(int x,int l,int r){
if(l==r){t[x]=arr[l];return ;}
int mid=(l+r)/2;
cre(x*2,l,mid);
cre(x*2+1,mid+1,r);
t[x]=max(t[x*2],t[x*2+1]);
}
int sol(int x,int l,int r,int ll,int rr){
if(l>rr||ll>r||ll>rr)return 0;
if(ll<=l&&r<=rr)return t[x];
int mid=(l+r)/2;
return max(sol(x*2,l,mid,ll,rr),sol(x*2+1,mid+1,r,ll,rr));
}
void init(int nn,vector<int> h){
int i,j,l,r,mid;
n=nn;
for(i=0;i<n;i++)arr[i+1]=h[i];
arr[n+1]=1e9;
cre(1,1,n);
for(i=0;i<20;i++)for(j=0;j<=n+1;j++)nxt[i][j]=n+1;
for(i=1;i<=n;i++){
l=i+1,r=n;
while(l<=r){
mid=(l+r)/2;
if(sol(1,1,n,i+1,mid)>arr[i])nxt[0][i]=mid,r=mid-1;
else l=mid+1;
}
}
for(i=1;i<20;i++)for(j=1;j<=n;j++)nxt[i][j]=nxt[i-1][nxt[i-1][j]];
return ;
}
int minimum_jumps(int a,int b,int c,int d){
a++,b++,c++,d++;
int i,mm,mr,pos,now,l,r,mid,v,val,ans;
mm=sol(1,1,n,b+1,c-1);
mr=sol(1,1,n,c,d);
if(mm>mr)return -1;
pos=-1;
l=a,r=b;
while(l<=r){
mid=(l+r)/2;
if(sol(1,1,n,mid,b)>mm)pos=mid,l=mid+1;
else r=mid-1;
}
if(pos!=-1&&arr[pos]<mr)return 1;
pos=-1;
l=a,r=b;
while(l<=r){
mid=(l+r)/2;
v=sol(1,1,n,mid,b);
if(v<mm)pos=mid,val=v,r=mid-1;
else l=mid+1;
}
if(pos==-1||val>mr)return -1;
pos=-1;
l=a,r=b;
while(l<=r){
mid=(l+r)/2;
if(sol(1,1,n,mid,b)<=val)pos=mid,l=mid+1;
else r=mid-1;
}
now=pos;
ans=1;
for(i=19;i>=0;i--){
if(arr[nxt[i][now]]<=mm)ans+=1<<i,now=nxt[i][now];
}
return ans;
}
Compilation message
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:71:9: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | if(sol(1,1,n,mid,b)<=val)pos=mid,l=mid+1;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
585 ms |
16768 KB |
Output is correct |
4 |
Correct |
2351 ms |
20388 KB |
Output is correct |
5 |
Correct |
1998 ms |
10568 KB |
Output is correct |
6 |
Correct |
2512 ms |
20388 KB |
Output is correct |
7 |
Correct |
1808 ms |
14752 KB |
Output is correct |
8 |
Correct |
2320 ms |
20348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Incorrect |
404 ms |
16848 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Incorrect |
372 ms |
9764 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Incorrect |
372 ms |
9764 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
585 ms |
16768 KB |
Output is correct |
4 |
Correct |
2351 ms |
20388 KB |
Output is correct |
5 |
Correct |
1998 ms |
10568 KB |
Output is correct |
6 |
Correct |
2512 ms |
20388 KB |
Output is correct |
7 |
Correct |
1808 ms |
14752 KB |
Output is correct |
8 |
Correct |
2320 ms |
20348 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
336 KB |
Output is correct |
13 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |