| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 871972 | vjudge1 | Rainforest Jumps (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define MAX 212345
int _n, _q;
vector<int> _h;
vector<int> h;
int up_r[MAX][21], up_l[MAX][21];
int build_r(int pos) {
int nxt = pos + 1;
while (nxt < h.size() && h[pos] > h[nxt]) nxt = build_r(nxt);
if (nxt == h.size()) up_r[pos][0] = pos;
else up_r[pos][0] = nxt;
return nxt;
}
int build_l(int pos) {
int nxt = pos - 1;
while (nxt > 0 && h[pos] > h[nxt]) nxt = build_l(nxt);
if (nxt == -1) up_l[pos][0] = pos;
else up_l[pos][0] = nxt;
return nxt;
}
void init(int N, vector<int> H) {
for (int i = 0; i < N; i++) h.push_back(H[i]);
memset(up_r, -1, sizeof up_r); memset(up_l, -1, sizeof up_l);
for (int i = 0; i < N; i++) {
if (up_r[i][0] == -1) build_r(i);
if (up_l[N - i - 1][0] == -1) build_l(N - i - 1);
}
int l = ceil(log2(N));
for (int j = 1; j <= l; j++)
for (int i = 0; i < N; i++) {
up_r[i][j] = up_r[up_r[i][j-1]][j-1];
up_l[i][j] = up_l[up_l[i][j-1]][j-1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (C == B + 1) {
if (up_r[B][0] > B && up_r[B][0] <= C) { return 1; }
else { return -1; }
}
int mid = B + 1;
for (int l = ceil(log2(C - 1 - mid + 1)); l >= 0; l--) { if (up_r[mid][l] < C) mid = up_r[mid][l]; }
int ans = 1123456789;
int b = B;
for (int l = ceil(log2(B - A + 1)); l >= 0; l--) { if (up_l[b][l] >= A && h[up_l[b][l]] < h[mid]) b = up_l[b][l]; }
if (h[b] < h[mid]) {
ans = 0; int _b = b;
for (int l = ceil(log2(D - b + 1)); l >= 0; l--) { if (up_r[_b][l] < C) { _b = up_r[_b][l]; ans += 1 << l; } }
ans = up_r[b][0] <= D ? ans + 1 : 1123456789;
}
if (h[b] >= h[mid] || up_l[b][0] >= A) {
int tmp_ans = 0;
b = h[b] <= h[mid] ? up_l[b][0] : b;
for (int l = ceil(log2(D - b + 1)); l >= 0; l--) { if (up_r[b][l] < C) { b = up_r[b][l]; ans += 1 << l; } }
tmp_ans = up_r[b][0] <= D ? tmp_ans + 1 : 1123456789;
ans = min(ans, tmp_ans);
}
//printf("%d\n", ans);
return ans == 1123456789 ? -1 : ans;
}
int main() {
/*
scanf("%d %d", &_n, &_q);
for (int i = 0, tmp = -1; i < _n; i++) { scanf("%d", &tmp); _h.push_back(tmp); }
init(_n, _h);
for (int i = 0; i < _q; i++) {
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
minimum_jumps(a, b, c, d);
}
//for (int i = 0; i < _n; i++) printf("%d ", up_l[i][0]);
//printf("\n");
//for (int i = 0; i < _n; i++) printf("%d ", up_r[i][0]);
//printf("\n");
*/
}