#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
/*
APIO 2021 – Rainforest Jumps
Cleaned and readable implementation.
We preprocess:
- nearest greater to left
- nearest greater to right
- binary lifting tables for repeated jumps
- "higher jump" table (jump to taller of left/right greater)
Query:
minimum_jumps(A, B, C, D)
*/
constexpr int MAX_LOG = 20;
int n; // number of positions (with sentinels)
vector<int> height; // heights (with sentinels)
vector<vector<int>> leftUp; // leftUp[k][i] = 2^k left-greater jumps
vector<vector<int>> rightUp; // rightUp[k][i] = 2^k right-greater jumps
vector<vector<int>> upHigher; // upHigher[k][i] = 2^k higher jumps
/* ---------------------------------------------------------- */
/* -------------------- PREPROCESSING ----------------------- */
/* ---------------------------------------------------------- */
void init(int N, vector<int> H) {
// Insert sentinels (very tall buildings)
height = H;
height.insert(height.begin(), INT_MAX);
height.push_back(INT_MAX);
n = height.size();
leftUp.assign(MAX_LOG, vector<int>(n));
rightUp.assign(MAX_LOG, vector<int>(n));
upHigher.assign(MAX_LOG, vector<int>(n));
// 1) Compute nearest greater to left
{
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && height[st.top()] <= height[i])
st.pop();
leftUp[0][i] = st.empty() ? i : st.top();
st.push(i);
}
}
// 2) Compute nearest greater to right
{
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && height[st.top()] <= height[i])
st.pop();
rightUp[0][i] = st.empty() ? i : st.top();
st.push(i);
}
}
// 3) Define higher jump (jump to taller of left/right greater)
for (int i = 0; i < n; i++) {
int L = leftUp[0][i];
int R = rightUp[0][i];
upHigher[0][i] = (height[L] > height[R]) ? L : R;
}
// 4) Build binary lifting tables
for (int k = 1; k < MAX_LOG; k++) {
for (int i = 0; i < n; i++) {
leftUp[k][i] = leftUp[k - 1][ leftUp[k - 1][i] ];
rightUp[k][i] = rightUp[k - 1][ rightUp[k - 1][i] ];
upHigher[k][i] = upHigher[k - 1][ upHigher[k - 1][i] ];
}
}
}
/* ---------------------------------------------------------- */
/* -------------------- HELPER FUNCTION --------------------- */
/* ---------------------------------------------------------- */
// Returns index of maximum height in [l, r]
int getMaxIndexInRange(int l, int r) {
for (int k = MAX_LOG - 1; k >= 0; k--) {
if (rightUp[k][l] <= r) {
l = rightUp[k][l];
}
}
return l;
}
/* ---------------------------------------------------------- */
/* ---------------------- MAIN QUERY ------------------------ */
/* ---------------------------------------------------------- */
int minimum_jumps(int A, int B, int C, int D) {
// Shift because of sentinel at beginning
A++; B++; C++; D++;
// Case 1: B is directly adjacent to C
if (B == C - 1) {
return (rightUp[0][B] <= D) ? 1 : -1;
}
// Find tallest building in middle interval
int midMax = getMaxIndexInRange(B + 1, C - 1);
// If B already taller than middle maximum
if (height[B] > height[midMax]) {
return (rightUp[0][B] <= D) ? 1 : -1;
}
int current = B;
int jumps = 0;
// Try climbing left while staying >= A and height constraint
for (int k = MAX_LOG - 1; k >= 0; k--) {
int nextLeft = leftUp[k][current];
if (A <= nextLeft && height[nextLeft] < height[midMax]) {
current = nextLeft;
}
}
// Try direct jump after left climbing
if (A <= leftUp[0][current]) {
if (rightUp[0][ leftUp[0][current] ] <= D)
return 1;
}
else {
// Climb using higher edges
for (int k = MAX_LOG - 1; k >= 0; k--) {
int nextHigher = upHigher[k][current];
if (height[nextHigher] <= height[midMax]) {
jumps += (1 << k);
current = nextHigher;
}
}
// If we reached the middle max
if (current == midMax) {
return (rightUp[0][current] <= D) ? jumps + 1 : -1;
}
// Try one extra left jump
if (leftUp[0][current] > 0 &&
rightUp[0][ leftUp[0][current] ] <= D) {
return jumps + 2;
}
}
// Otherwise sweep right toward C
for (int k = MAX_LOG - 1; k >= 0; k--) {
if (rightUp[k][current] < C) {
jumps += (1 << k);
current = rightUp[k][current];
}
}
return (C <= rightUp[0][current] && rightUp[0][current] <= D)
? jumps + 1
: -1;
}
