#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e5 + 5;
using namespace std;
int st0[mxN][32],st1[mxN][32];
pii seg[1000005];
int NN;
pii query(int l,int r,int ind,int s,int e){
if(l > e || r < s) return {0,0};
if(l >= s && r <= e) return seg[ind];
int md = (l + r) / 2;
return max(query(l,md,ind * 2,s,e),query(md + 1,r,ind * 2 + 1,s,e));
}
vector<int>h;
int find(int l,int r,int val,bool sd){
// if(l == 19) cout<<l<<' '<<r<<'\n';
if(l > r || query(1,NN,1,l,r).F < val) return -1;
if(l == r) return query(1,NN,1,l,r).S;
int md = (l + r) / 2;
auto a = query(1,NN,1,l,md), b = query(1,NN,1,md + 1,r);
if (sd){
if(a.F > val) return find(l,md,val,sd);
return find(md + 1,r,val,sd);
}else{
if(b.F > val) return find(md + 1,r,val,sd);
return find(l,md,val,sd);
}
}
int solve(int x,int val,int C,int D){
int ans = 0;
for(int i = 20;i >= 0;i--){
if(h[st1[x][i]] < val && !(st1[st1[x][i]][0] >= C && st1[st1[x][i]][0] <= D) && !(st0[st1[x][i]][0] >= C && st0[st1[x][i]][0] <= D)){
x = st1[x][i];
ans += (1 << i);
// cout<<i<<' '<<x<<' '<<ans<<'\n';
}
}
// cout<<st1[x][0]<<' '<<C<<' '<<D<<'\n';
if((st1[x][0] >= C && st1[x][0] <= D) || (st0[x][0] >= C && st0[x][0] <= D)) return ans + 1;
if(h[st1[x][0]] < val) {
ans++;
x = st1[x][0];
}
for(int i = 20;i >= 0;i--){
if(h[st0[x][i]] < val && !(st0[x][i] >= C && st0[x][i] <= D)){
x = st0[x][i];
ans += (1 << i);
}
}
ans++;
return {ans};
}
void init(int N, vector<int> H) {
NN = exp2(ceil(log2(N)));
for(int i = 0;i < N;i++){
seg[i + NN] = {H[i],i};
}
h = H;
for(int i = NN - 1;i;i--) seg[i] = max(seg[i * 2],seg[i * 2 + 1]);
for(int i = 0;i < N;i++){
int a = find(1,i,H[i],0),b = find(i + 2,N,H[i],1);
// cout<<i<<' '<<a<<' '<<b<<'\n';
if(h[a] < h[b]) swap(a,b);
if(a == -1) a = i;
if(b == -1) b = i;
st1[i][0] = a;
st0[i][0] = b;
}
for(int pw = 1;pw <= 20;pw++){
for(int i = 0;i < N;i++){
st1[i][pw] = st1[st1[i][pw - 1]][pw - 1];
st0[i][pw] = st0[st0[i][pw - 1]][pw - 1];
// cout<<st1[i][pw]<<' ';
}
// cout<<'\n';
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++;
B++;
C++;
D++;
// if(A != B || C != D) assert(1);
int mxA = query(1,NN,1,A,B).F,mxidA = query(1,NN,1,A,B).S,mxC = query(1,NN,1,C,D).F,mxidC = query(1,NN,1,C,D).S;
// // cout<<mxA<<' '<<mxidA<<' '<<mxC<<' '<<mxidC<<'\n';
if(query(1,NN,1,B,C - 1).F > mxC) return -1;
int x;
if(mxC > mxA) x = mxidA;
else{
x = find(A,B,mxC,0);
x = query(1,NN,1,x + 2,B).S;
}
return solve(x,mxC,C - 1,D - 1);
}
// 20 3
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
// 0 0 6 6
// 3 4 5 6
// 2 2 5 6
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |