#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
vector<int> minV;
vector<int> maxV;
vector<vector<int>> liftingMin;
vector<vector<int>> liftingMax;
void init(int N, std::vector<int> H) {
n = N, h = H;
minV = maxV = vector<int>(n);
liftingMin = liftingMax = vector<vector<int>>(n, vector<int>(30, -1));
{
stack<pair<int, int>> st;
st.push({1e9, -1});
for (int i = 0; i < n; i++) {
while (st.top().first < h[i]) st.pop();
minV[i] = st.top().second;
st.push({h[i], i});
}
}
{
stack<pair<int, int>> st;
st.push({1e9, -1});
for (int i = n-1; i >= 0; i--) {
while (st.top().first < h[i]) st.pop();
maxV[i] = st.top().second;
st.push({h[i], i});
}
}
//for (int x : minV) cout << x << " "; cout << endl;
//for (int x : maxV) cout << x << " "; cout << endl;
//return;
for (int i = 0; i < n; i++) {
if (minV[i] == -1 && maxV[i] == -1) continue;
if (minV[i] == -1) {
minV[i] = maxV[i];
} else if (maxV[i] == -1) {
maxV[i] = minV[i];
} else if (h[minV[i]] > h[maxV[i]]) swap(minV[i], maxV[i]);
}
//for (int x : minV) cout << x << " "; cout << endl;
//for (int x : maxV) cout << x << " "; cout << endl;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) v.push_back({h[i], i});
sort(v.rbegin(), v.rend());
for (int j = 1; j < n; j++) {
int i = v[j].second;
liftingMin[i][0] = minV[i];
liftingMax[i][0] = maxV[i];
for (int j = 1; j < 30; j++) {
if (liftingMin[i][j-1] != -1) liftingMin[i][j] = liftingMin[liftingMin[i][j-1]][j-1];
if (liftingMax[i][j-1] != -1) liftingMax[i][j] = liftingMax[liftingMax[i][j-1]][j-1];
}
}
//for (int i = 0; i < n; i++) {
//for (int j = 0; j < 5; j++) cout << liftingMax[i][j] << " ";
//cout << endl;
//}
}
pair<int, int> blift(vector<vector<int>>& g, int u, int v) {
for (int i = -1; i < 30; i++) {
if (g[u][i + 1] == -1 || h[g[u][i + 1]] > h[v]) {
if (i == -1) return {0, u};
else {
//cout << "END AT " << g[u][i] << endl;
pair<int, int> p = blift(g, g[u][i], v);
return {(1<<i) + p.first, p.second};
}
}
}
}
vector<int> dp;
int dpf(int i) {
if (dp[i] != -1) return dp[i];
if (minV[i] == -1) return dp[i] = 2e9;
return min(dpf(minV[i]), dpf(maxV[i])) + 1;
}
int minimum_jumps(int A, int B, int C, int D) {
if (A == B && C == D) {
pair<int, int> p = blift(liftingMax, A, D);
//cout << p.first << " " << p.second << endl;
pair<int, int> q = blift(liftingMin, p.second, D);
if (h[q.second] != h[D]) return -1;
else return p.first + q.first;
} else {
dp = vector<int>(n, -1);
for (int i = C; i <= D; i++) dp[i] = 0;
int mn = 2e9;
for (int i = A; i <= B; i++) {
//cout << dpf(i) << endl;
mn = min(mn, dpf(i));
}
if (mn == 2e9) return -1;
return mn;
}
}
//7 0
//3 2 1 6 4 5 7
int main() {
int N, Q;
//assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
N = 7;
Q = 10000;
H = vector<int>{3, 2, 1, 6, 4, 5, 7};
//H = vector<int>{3, 2, 1, 6, 4, 5, 7, 8, 10, 12, 11, 9};
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;
}
Compilation message
jumps.cpp: In function 'std::pair<int, int> blift(std::vector<std::vector<int> >&, int, int)':
jumps.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
80 | }
| ^
jumps.cpp: In function 'int main()':
jumps.cpp:116:23: warning: 'N' is used uninitialized in this function [-Wuninitialized]
116 | std::vector<int> H(N);
| ^
/usr/bin/ld: /tmp/ccimkUky.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccb7V2nA.o:jumps.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
