| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1302806 | icebear | Rainforest Jumps (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
/* AUTHOR: TUAN ANH - BUI */
// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) return x = y, true;
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) return x = y, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
/*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 27092008;
const ll INF = (ll)1e18 + 27092008;
const int N = 2e5 + 5;
int h[N], L[N][20], R[N][20], high[N][20], low[N][20];
void init(int N, vector<int> H) {
REP(i, N) h[i] = H[i];
stack<int> st;
REP(i, N) {
while(!st.empty() && H[st.top()] < H[i]) st.pop();
L[i][0] = (st.empty() ? N : st.top());
st.push(i);
}
st = stack<int>();
RED(i, N) {
while(!st.empty() && H[st.top()] < H[i]) st.pop();
R[i][0] = (st.empty() ? N : st.top());
st.push(i);
}
REP(i, N) {
if (H[L[i][0]] > H[R[i][0]]) {
high[i][0] = L[i][0];
low[i][0] = R[i][0];
} else {
high[i][0] = R[i][0];
low[i][0] = L[i][0];
}
}
REP(j, 20) L[N][j] = R[N][j] = high[N][j] = low[N][j] = N;
h[N] = inf;
FOR(j, 1, 19) REP(i, N) {
L[i][j] = L[L[i][j - 1]][j - 1];
R[i][j] = R[R[i][j - 1]][j - 1];
low[i][j] = low[low[i][j - 1]][j - 1];
high[i][j] = high[high[i][j - 1]][j - 1];
}
}
int get_max(int left, int right, int limit) {
RED(j, 20) if (L[right][j] >= left && h[L[right][j]] < limit)
right = L[right][j];
return right;
}
int minimum_jumps(int A, int B, int C, int D) {
int ans = 0, max_right = get_max(C, D, inf), max_left = get_max(A, B, h[max_right]);
RED(j, 20) if (h[high[max_left][j]] < h[max_right] && high[max_left][j] < C && low[max_left][j] < C && R[max_left][j] < C) {
ans += MASK(j);
max_left = high[max_left][j];
}
if (C <= high[max_left][0] && high[max_left][0] <= D) return ans + 1;
RED(j, 20) if (h[R[max_left][j]] < h[max_right] && R[max_left][j] < C) {
ans += MASK(j);
max_left = R[max_left][j];
}
return (C <= R[max_left][0] && R[max_left][0] <= D ? ans + 1 : -1);
}
int main() {
freopen("gen.inp", "r", stdin);
freopen("gen.out", "w", stdout);
int N; cin >> N;
vector<int> H(N);
for(int &x : H) cin >> x;
init(N, H);
int Q; cin >> Q;
while(Q--) {
int A, B, C, D;
cin >> A >> B >> C >> D;
cout << minimum_jumps(A, B, C, D) << '\n';
}
// init(7, {3, 2, 1, 6, 4, 5, 7});
// cout << minimum_jumps(4, 4, 6, 6) << '\n' << minimum_jumps(1, 3, 5, 6) << '\n' << minimum_jumps(0, 1, 2, 2);
return 0;
}