# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1047860 | Maite_Morale | Rainforest Jumps (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 500005
#define oo 1e18
#define pll pair<ll,ll>
#define F first
#define S second
const ll bts=20;
pll p[MAX],s[bts+10][MAX],t[bts+10][MAX];
ll d[MAX],N;
pll query(ll x,ll y){
if(x>y)return {0,N};
ll c=log2l(abs(x-y)+1);
return max(t[c][x],t[c][y-(1LL<<c)+1]);
}
void init(int n, std::vector<int> H) {
H.push_back(0);N=n;pll rt={0,n};
for(int i=0;i<=n;i++){
t[0][i]={H[i],i};
rt=max(rt,t[0][i]);
}
for(int i=1;i<=bts;i++){
for(int j=0;j<=n;j++){
t[i][j]=max(t[i-1][j],t[i-1][j+(1LL<<(i-1))]);
}
}
queue<pair<ll,pll>> q;
q.push({rt.S,{0,n-1}});
d[n]=0;s[0][n]={n,n};
d[rt.S]=1;s[0][rt.S]={n,n};
while(!q.empty()){
pair<ll,pll> u=q.front();q.pop();
pair<ll,pll> h1={query(u.S.F,u.F-1).S,{u.S.F,u.F-1}};
if(h1.F!=n){
d[h1.F]=d[u.F]+1;
p[h1.F]={h1.S.F-1,h1.S.S+1};
s[0][h1.F].F=u.S.F-1;
s[0][h1.F].S=u.F;
q.push(h1);
}
pair<ll,pll> h2={query(u.F+1,u.S.S).S,{u.F+1,u.S.S}};
if(h2.F!=n){
d[h2.F]=d[u.F]+1;
p[h2.F]={h2.S.F-1,h2.S.S+1};
s[0][h2.F].F=u.S.S+1;
s[0][h2.F].S=u.F;
q.push(h2);
}
}
for(int i=0;i<=n;i++){
if(s[0][i].F==-1)s[0][i].F=n;
if(s[0][i].S==-1)s[0][i].S=n;
}
for(int i=1;i<=bts;i++){
for(int j=0;j<=n;j++){
s[i][j].F=s[i-1][s[i-1][j].F].F;
s[i][j].S=s[i-1][s[i-1][j].S].S;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
swap(B,C);
if(A<=p[B].F)return -1;
ll r=0;
for(int i=bts;i>=0;i--){
if(d[s[i][A].F]>=d[B]){
r+=(1LL<<i);
A=s[i][A].F;
}
}
for(int i=bts;i>=0;i--){
if(d[s[i][A].S]>=d[B]){
r+=(1LL<<i);
A=s[i][A].S;
}
}
return r;
}
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}
/*
7 4
3 2 1 6 4 5 7
4 4 6 6
1 1 5 5
0 0 2 2
5 5 6 6
*/