| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1295510 | icebear | 밀림 점프 (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
/*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 2e5 + 5;
int n, q, h[N];
int low[N][20], high[N][20];
void init(int N, int H[]) {
n = N;
REP(i, n) h[i] = H[i];
h[n] = inf;
stack<int> st;
REP(i, n) {
while(!st.empty() && h[st.top()] < h[i]) st.pop();
low[i][0] = (st.empty() ? n : st.top());
st.push(i);
}
st = stack<int>();
RED(i, n) {
while(!st.empty() && h[st.top()] < h[i]) st.pop();
high[i][0] = (st.empty() ? n : st.top());
st.push(i);
}
REP(j, 20) low[n][j] = high[n][j] = n;
REP(i, n) {
int &a = low[i][0], &b = high[i][0];
if (a == n || (a != n && b != n && h[a] > h[b])) swap(a, b);
}
FOR(j, 1, 19) REP(i, n) {
low[i][j] = low[low[i][j - 1]][j - 1];
high[i][j] = high[high[i][j - 1]][j - 1];
}
}
int minimum_jumps(int a, int b, int c, int d) {
if (h[a] > h[c]) return -1;
int ans = 0;
RED(j, 20) if (h[high[a][j]] < h[c]) {
a = high[a][j];
ans |= MASK(j);
}
RED(j, 20) if (h[low[a][j]] < h[c]) {
a = low[a][j];
ans |= MASK(j);
}
return low[a][0] == c ? ans + 1 : -1;
}