# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
857449 | chanhchuong123 | Rainforest Jumps (APIO21_jumps) | C++14 | 786 ms | 45060 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define task ""
const int MAX = 200020;
int n, q;
stack<int> st;
int H[MAX], dp[18][MAX];
int rg[18][MAX], hg[18][MAX];
#define combine(x, y) (x == -1 ? y : y == -1 ? x : H[x] > H[y] ? x : y)
int getMax(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return combine(dp[k][l], dp[k][r - (1 << k) + 1]);
}
void init(int _n, vector<int> _H) {
n = _n;
for (int i = 0; i < n; ++i) {
H[i] = _H[i];
}
st = stack<int> {};
for (int i = 0; i <= n - 1; ++i) {
while (st.size() && H[st.top()] < H[i]) st.pop();
hg[0][i] = st.size() ? st.top() : -1; st.push(i);
}
st = stack<int> {};
for (int i = n - 1; i >= 0; --i) {
while (st.size() && H[st.top()] < H[i]) st.pop();
rg[0][i] = st.size() ? st.top() : -1; st.push(i);
}
for (int i = 0; i < n; ++i) {
dp[0][i] = i;
hg[0][i] = combine(hg[0][i], rg[0][i]);
}
for (int j = 1; j <= 17; ++j) {
for (int i = 0; i < n; ++i) {
if (hg[j - 1][i] != -1) hg[j][i] = hg[j - 1][hg[j - 1][i]]; else hg[j][i] = -1;
if (rg[j - 1][i] != -1) rg[j][i] = rg[j - 1][rg[j - 1][i]]; else rg[j][i] = -1;
if (i + (1 << j) <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int BC = getMax(B, C - 1), CD = getMax(C, D);
if (H[BC] > H[CD]) return -1;
int l = A - 1, r = B;
while (r - l > 1) {
int mid = l + r >> 1;
if (H[getMax(mid, B)] < H[CD]) r = mid; else l = mid;
}
int st = getMax(r, B), res = 0;
if (C <= rg[0][st] && rg[0][st] <= D) return 1;
for (int j = 17; j >= 0; --j) if (hg[j][st] != -1) {
if (rg[0][hg[j][st]] != -1 && rg[0][hg[j][st]] < C) {
st = hg[j][st];
res += 1 << j;
}
}
int nx = hg[0][st];
if (rg[0][nx] <= D) {
st = nx; ++res;
if (C <= rg[0][nx] && rg[0][nx] <= D) return res + 1;
}
for (int j = 17; j >= 0; --j) if (rg[j][st] != -1) {
if (rg[j][st] < C) {
st = rg[j][st];
res += 1 << j;
}
}
res += 1; st = rg[0][st];
if (st < C) return -1;
if (st > D) return -1;
return res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |