#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
#define rep(i, a, b) for(ll i=a; i<b; i++)
#define repd(i, a, b) for(ll i=a; i>=b; i--)
int n, h[int(2e5+10)];
int jmp_l[int(2e5+10)][30];
int jmp_r[int(2e5+10)][30];
int jmp_mx[int(2e5+10)][30];
void init(int N, vo<int> H) {
n=N+2;
h[0]=1e8;
rep(i, 0, N)
h[i+1]=H[i];
h[n-1]=1e8;
stack<int> st;
rep(i, 0, n) {
while(sz(st) && h[st.top()]<h[i])
jmp_r[st.top()][0]=i, st.pop();
st.push(i);
}
while(sz(st))
st.pop();
repd(i, n-1, 0) {
while(sz(st) && h[st.top()]<h[i])
jmp_l[st.top()][0]=i, st.pop();
st.push(i);
}
rep(i, 0, n) {
jmp_mx[i][0]=jmp_r[i][0];
if(h[jmp_l[i][0]]>h[jmp_r[i][0]])
jmp_mx[i][0]=jmp_l[i][0];
}
rep(i, 1, 30)
rep(k, 0, n) {
jmp_l[k][i]=jmp_l[jmp_l[k][i-1]][i-1];
jmp_r[k][i]=jmp_r[jmp_r[k][i-1]][i-1];
jmp_mx[k][i]=jmp_mx[jmp_mx[k][i-1]][i-1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
if(B+1==C) {
if(jmp_r[B][0]>D)
return -1;
else
return 1;
}
int ind=B+1;
repd(i, 29, 0)
if(jmp_r[ind][i]<C)
ind=jmp_r[ind][i];
if(h[B]>h[ind]) {
if(jmp_r[B][0]>D)
return -1;
else
return 1;
}
int cur=B;
repd(i, 29, 0)
if(h[jmp_l[cur][i]]<h[ind] && jmp_l[cur][i]>=A)
cur=jmp_l[cur][i];
int ans=0;
if(jmp_l[cur][0]>=A) {
if(jmp_r[jmp_l[cur][0]][0]<=D)
return 1;
}
else {
repd(i, 29, 0)
if(h[jmp_mx[cur][i]]<=h[ind]) {
cur=jmp_mx[cur][i];
ans+=1<<i;
if(h[cur]==h[ind]) {
if(jmp_r[cur][0]>D)
return -1;
else
return ans+1;
}
if(jmp_l[cur][0] && jmp_r[jmp_l[cur][0]][0]<=D)
return ans+2;
}
repd(i, 29, 0)
if(jmp_r[cur][i]<C) {
cur=jmp_r[cur][i];
ans+=1<<i;
}
if(jmp_r[cur][0]>=C && jmp_r[cur][0]<=D)
return ans+1;
else
return -1;
}
Compilation message
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:115:1: error: expected '}' at end of input
115 | }
| ^
jumps.cpp:57:47: note: to match this '{'
57 | int minimum_jumps(int A, int B, int C, int D) {
| ^
jumps.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
115 | }
| ^
