| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 858355 | chanhchuong123 | 밀림 점프 (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define task ""
const int MAX = 200020;
int n, q;
int H[MAX];
stack<int> st;
int dp[18][MAX], rg[18][MAX], hi[18][MAX];
#define combine(x, y) (H[(x)] < H[(y)] ? y : x)
void init(int N, vector<int> _H) {
n = N;
for (int i = 0; i < n; ++i) {
H[i + 1] = _H[i];
}
H[0] = H[n + 1] = n + 1; st.push(0);
for (int i = 1; i <= n; ++i) {
while (H[st.top()] < H[i]) st.pop();
hi[0][i] = st.top(); st.push(i);
}
st.push(n + 1); rg[0][0] = rg[0][n + 1] = n + 1;
for (int i = n; i >= 1; --i) {
while (H[st.top()] < H[i]) st.pop();
rg[0][i] = st.top(); st.push(i);
}
for (int i = 1; i <= n; ++i) {
dp[0][i] = i;
hi[0][i] = combine(hi[0][i], rg[0][i]);
}
for (int j = 1; j <= 17; ++j) {
for (int i = 0; i <= n + 1; ++i) {
hi[j][i] = hi[j - 1][hi[j - 1][i]];
rg[j][i] = rg[j - 1][rg[j - 1][i]];
if (i + (1 << j) - 1 <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
}
}
}
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]);
}
bool in(int x, int C, int D) {
return C <= x && x <= D;
}
int minimum_jumps(int A, int B, int C, int D) {
++A;
++B;
++C;
++D;
int CD = getMax(C, D);
int BC = getMax(B, C - 1);
if (H[BC] > H[CD]) return -1;
int l = A, r = B;
while (l <= r) {
int m = l + r >> 1;
if (H[getMax(m, B)] < p)
r = m - 1; else l = m + 1;
}
int st = getMax(l, B);
if (in(rg[0][st], C, D)) return 1;
int res = 0;
for (int j = 17; j >= 0; --j) if (rg[0][hi[j][st]] < C) {
st = hi[j][st];
res += 1 << j;
}
int nt = hi[0][st];
if (rg[0][nt] <= D) {
st = nt; ++res;
if (in(rg[0][nt], C, D)) return res + 1;
}
for (int j = 17; j >= 0; --j) if (rg[j][st] < C) {
st = rg[j][st];
res += 1 << j;
}
return res + 1;
}