| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1165736 | antonn | 밀림 점프 (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;
for (int i = 0; i < n; ++i) {
anc[h][i] = anc[h - 1][anc[h - 1][i]];
}
}
}
int get(int i, int c) {
for (int h = L - 1; h >= 0; --h) {
if (anc[h][i] < c) {
i = anc[h][i];
}
}
return anc[0][i];
}
int dist(int i, int j) {
int ans = 0;
for (int h = L - 1; h >= 0; --h) {
if (anc[h][i] <= j) {
ans += (1 << h);
i = anc[h][i];
}
}
return ans;
}
int minimum_jump(int a, int b, int c, int d) {
int ans = 1e9;
for (int i = a; i <= b; ++i) {
if (get(i, c) <= d) {
ckmin(ans, dist(i, get(i, c)));
}
}
if (ans == 1e9) ans = -1;
return ans;
}
/**
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
int h[n];
for (int i = 0; i < n; ++i) cin >> h[i];
init(n, h);
for (int i = 0; i < q; ++i) { int a, b, c, d; cin >> a >> b >> c >> d; cout << minimum_jump(a, b, c, d) << "\n"; }
}
**/
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/