| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1195007 | ainunnajib | Rainforest Jumps (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int MAXLOG = 18;
const int MAXNODE = 200000 * 20; // ~4e6, but we allocate up to 20e6 nodes for safety
int N, Q;
int H[MAXN];
int Lgr[MAXN], Rgr[MAXN];
int parentArr[MAXN], skipArr[MAXN];
vector<int> children[MAXN];
int depthArr[MAXN];
int tin[MAXN], tout[MAXN], timer_dfs = 0;
// For binary lifting on skip edges
int up[MAXN][MAXLOG];
int skipLen[MAXN][MAXLOG];
// For RMQ on H
int stIdx[MAXLOG][MAXN];
int lg2[MAXN+1];
// Segment-tree-of-segment-trees for 2D query (index range & subtree range)
int *root;
struct SegNode { int l, r, mh, mi; } seg[20000000];
int segCnt = 1;
// Update the inner (tin-dimension) segtree
int updateTin(int s, int tl, int tr, int pos, int h, int idx) {
if (!s) {
s = segCnt++;
seg[s].l = seg[s].r = 0;
seg[s].mh = h;
seg[s].mi = idx;
} else if (h > seg[s].mh || (h == seg[s].mh && idx < seg[s].mi)) {
seg[s].mh = h;
seg[s].mi = idx;
}
if (tl == tr) return s;
int mid = (tl + tr) >> 1;
if (pos <= mid)
seg[s].l = updateTin(seg[s].l, tl, mid, pos, h, idx);
else
seg[s].r = updateTin(seg[s].r, mid+1, tr, pos, h, idx);
return s;
}
// Update the outer (index-dimension) segtree
void updateIdx(int id, int l, int r, int pos, int tinpos, int h, int idx) {
root[id] = updateTin(root[id], 1, N, tinpos, h, idx);
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) updateIdx(id<<1, l, mid, pos, tinpos, h, idx);
else updateIdx(id<<1|1, mid+1, r, pos, tinpos, h, idx);
}
// Query the inner segtree for max (h,idx)
pair<int,int> queryTin(int s, int tl, int tr, int ql, int qr) {
if (!s || qr < tl || tr < ql) return {-1, -1};
if (ql <= tl && tr <= qr) return {seg[s].mh, seg[s].mi};
int mid = (tl + tr) >> 1;
auto a = queryTin(seg[s].l, tl, mid, ql, qr);
auto b = queryTin(seg[s].r, mid+1, tr, ql, qr);
if (a.first > b.first) return a;
if (b.first > a.first) return b;
if (a.second < 0) return b;
if (b.second < 0) return a;
return a.second < b.second ? a : b;
}
// Query the outer segtree on [ql,qr] and inner on [tl,tr]
pair<int,int> queryIdx(int id, int l, int r, int ql, int qr, int tl, int tr) {
if (qr < l || r < ql) return {-1, -1};
if (ql <= l && r <= qr) {
return queryTin(root[id], 1, N, tl, tr);
}
int mid = (l + r) >> 1;
auto a = queryIdx(id<<1, l, mid, ql, qr, tl, tr);
auto b = queryIdx(id<<1|1, mid+1, r, ql, qr, tl, tr);
if (a.first > b.first) return a;
if (b.first > a.first) return b;
if (a.second < 0) return b;
if (b.second < 0) return a;
return a.second < b.second ? a : b;
}
// Build nearest-greater arrays
void buildNearest() {
stack<int> st;
for (int i = 0; i < N; i++) {
while (!st.empty() && H[st.top()] < H[i]) st.pop();
Lgr[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = N-1; i >= 0; i--) {
while (!st.empty() && H[st.top()] < H[i]) st.pop();
Rgr[i] = st.empty() ? -1 : st.top();
st.push(i);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
for (int i = 0; i < N; i++) cin >> H[i];
buildNearest();
int rootIdx = 0;
// Determine parent & skip for each node in the Cartesian tree
for (int i = 0; i < N; i++) {
int l = Lgr[i], r = Rgr[i];
if (l<0 && r<0) {
parentArr[i] = -1;
skipArr[i] = -1;
rootIdx = i;
} else if (l<0) {
parentArr[i] = r;
skipArr[i] = -1;
} else if (r<0) {
parentArr[i] = l;
skipArr[i] = -1;
} else if (H[l] < H[r]) {
parentArr[i] = l;
skipArr[i] = r;
} else {
parentArr[i] = r;
skipArr[i] = l;
}
}
// Build adjacency in Cartesian tree
for (int i = 0; i < N; i++) {
if (parentArr[i] >= 0)
children[parentArr[i]].push_back(i);
}
// Iterative DFS to compute tin, tout, depth
vector<int> st_node, st_ptr(N);
st_node.push_back(rootIdx);
depthArr[rootIdx] = 0;
st_ptr[rootIdx] = 0;
while (!st_node.empty()) {
int u = st_node.back();
if (st_ptr[u] == 0) tin[u] = ++timer_dfs;
if (st_ptr[u] < (int)children[u].size()) {
int v = children[u][st_ptr[u]++];
depthArr[v] = depthArr[u] + 1;
st_ptr[v] = 0;
st_node.push_back(v);
} else {
tout[u] = timer_dfs;
st_node.pop_back();
}
}
// Prepare binary lifting for skip edges
for (int i = 0; i < N; i++) {
up[i][0] = skipArr[i] >= 0 ? skipArr[i] : -1;
skipLen[i][0] = skipArr[i] >= 0 ? 1 : 0;
}
for (int k = 1; k < MAXLOG; k++) {
for (int i = 0; i < N; i++) {
int m = up[i][k-1];
if (m >= 0) {
up[i][k] = up[m][k-1];
skipLen[i][k] = skipLen[i][k-1] + skipLen[m][k-1];
} else {
up[i][k] = -1;
skipLen[i][k] = skipLen[i][k-1];
}
}
}
// Build sparse table for RMQ on H
lg2[1] = 0;
for (int i = 2; i <= N; i++) lg2[i] = lg2[i>>1] + 1;
for (int i = 0; i < N; i++) stIdx[0][i] = i;
for (int k = 1; k < MAXLOG; k++) {
for (int i = 0; i + (1<<k) <= N; i++) {
int a = stIdx[k-1][i];
int b = stIdx[k-1][i + (1<<(k-1))];
stIdx[k][i] = (H[a] >= H[b] ? a : b);
}
}
auto rmqIdx = [&](int l, int r){
int len = r - l + 1;
int k = lg2[len];
int a = stIdx[k][l];
int b = stIdx[k][r - (1<<k) + 1];
return H[a] >= H[b] ? a : b;
};
// Build 2D segment tree
root = new int[4*N]();
for (int i = 0; i < N; i++) {
updateIdx(1, 0, N-1, i, tin[i], H[i], i);
}
// Answer queries
while (Q--) {
int A,B,C,D;
cin >> A >> B >> C >> D;
// find target y = index of max H in [C,D]
int y = rmqIdx(C, D);
// find best source s in [A,B] ∩ subtree(y)
auto qr = queryIdx(1, 0, N-1, A, B, tin[y], tout[y]);
int sidx = qr.second;
if (sidx < 0) {
cout << "-1\n";
continue;
}
// compute minimal jumps from sidx up to y
int cur = sidx, ans = 0;
for (int k = MAXLOG-1; k >= 0; k--) {
int nxt = (cur>=0 ? up[cur][k] : -1);
if (nxt >= 0 && depthArr[nxt] >= depthArr[y]) {
ans += skipLen[cur][k];
cur = nxt;
}
}
// finish with parent-by-one jumps
ans += depthArr[cur] - depthArr[y];
cout << ans << "\n";
}
return 0;
}