| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1311023 | vtnoo | Rainforest Jumps (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
//~ #include "jumps.h"
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<int,int>
using namespace std;
const int MAXN=2e5+5,LOG=20,INF=1e9;
int h[MAXN],sl[MAXN],sr[MAXN],upf[MAXN][LOG],ups[MAXN][LOG],upl[MAXN][LOG],n;
vi adj[MAXN];
void init(int N, std::vector<int> H) {
n=N;
stack<ii>mn;
L(i,0,N-1){
while(sz(mn)&&mn.top().fst<=H[i]){
mn.pop();
}
sl[i]=sz(mn)?mn.top().snd:i;
mn.push({H[i],i});
}
while(sz(mn))mn.pop();
R(i,N-1,0){
while(sz(mn)&&mn.top().fst<=H[i]){
mn.pop();
}
sr[i]=sz(mn)?mn.top().snd:i;
mn.push({H[i],i});
}
L(i,0,N-1)h[i]=H[i];
L(i,0,N-1){
if(h[sl[i]]>h[sr[i]]){
upf[i][0]=sl[i];
ups[i][0]=sr[i];
}else{
upf[i][0]=sr[i];
ups[i][0]=sl[i];
}
upl[i][0]=sl[i];
}
L(i,1,LOG-1){
L(j,0,N-1){
upl[j][i]=upl[upl[j][i-1]][i-1];
upf[j][i]=upf[upf[j][i-1]][i-1];
ups[j][i]=ups[ups[j][i-1]][i-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(A>=C&&A<=D)return 0;
if(B>=C&&B<=D)return 0;
int u=B;
R(i,LOG-1,0){
if(upl[u][i]==u)continue;
if(sr[upl[u][i]]==upl[u][i])continue;
if(upl[u][i]<A)continue;
if(sr[upl[u][i]]<=D){
u=upl[u][i];
}
}
//~ cout<<u<<endl;
int ans=0;
R(i,LOG-1,0){
if(upf[u][i]==u)continue;
if(upf[u][i]<C){
u=upf[u][i];
ans+=(1<<i);
}
}
//~ cout<<u<<endl;
if(C<=upf[u][0]&&upf[u][0]<=D)return ans+1;
R(i,LOG-1,0){
if(ups[u][i]==u)continue;
if(ups[u][i]<C){
u=ups[u][i];
ans+=(1<<i);
}
}
//~ cout<<u<<endl;
if(C<=ups[u][0]&&ups[u][0]<=D)return ans+1;
return -1;
}
int main(){
int N,Q;cin>>N>>Q;
vi H(N);
L(i,0,N-1)cin>>H[i];
init(N,H);
while(Q--){
int A,B,C,D;cin>>A>>B>>C>>D;
cout<<minimum_jumps(A,B,C,D)<<endl;
}
}