# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1165736 | antonn | Rainforest Jumps (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 2e5 + 7;
const int L = 20;
int r[N], anc[L][N];
void init(int n, int h[]) {
vector<int> stk;
for (int i = n - 1; i >= 0; --i) {
while (!stk.empty() && h[i] > h[stk.back()]) stk.pop_back();
if (!stk.empty()) r[i] = stk.back();
if (stk.empty()) r[i] = n;
stk.push_back(i);
}
for (int i = 0; i < n; ++i) anc[0][i] = r[i];
anc[0][n] = n;
for (int h = 1; h < L; ++h) {
anc[h][n] = n;