| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 860259 | mychecksedad | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<jumps.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;
int n, L[N], R[N], up[N][K][2], dp[N][K], le[N][K];
vector<int> H;
// vector<array<int, 2>> T[N];
int maxx(int l, int r){
int k = int(log2(r-l+1));
return max(dp[l][k], dp[r-(1<<k)+1][k]);
}
// void build(int l, int r, int k){
// if(l == r){
// T[k].pb(array<int, 2>{H[l-1], l-1});
// return;
// }
// int m = l+r>>1;
// build(l, m, k<<1);
// build(m+1, r, k<<1|1);
// int p = 0;
// for(int i = 0; i < T[k<<1].size(); ++i){
// while(p < T[k<<1|1].size() && T[k<<1|1][p] < T[k<<1][i]){
// T[k].pb(T[k<<1|1][p]);
// ++p;
// }
// T[k].pb(T[k<<1][i]);
// }
// while(p < T[k<<1|1].size())
// T[k].pb(T[k<<1|1][p]), ++p;
// // cout << l << ' ' << r << '\n';
// // for(auto p: T[k]) cout << p[0] << ' ' << p[1] << " | ";
// // en;
// }
// array<int, 2> get(int l, int r, int ql, int qr, int k, int val){
// if(ql > r || l > qr) return {-1, -1};
// if(ql <= l && r <= qr){
// int pos = lower_bound(all(T[k]), array<int, 2>{val, -1}) - T[k].begin();
// // cout << l << ' ' << r << ' ' << ql << ' ' << qr << ' ' << val << '\n';
// --pos;
// if(pos >= 0){
// // cout << T[k][pos][0] << ' ' << T[k][pos][1] << '\n';
// return T[k][pos];
// }
// return {-1, -1};
// }
// int m = l+r>>1;
// auto L = get(l, m, ql, qr, k<<1, val);
// auto R = get(m+1, r, ql, qr, k<<1|1, val);
// if(L[0] < R[0])
// return R;
// return L;
// }
void init(int _n, vector<int> h){
n = _n;
H = h;
H.pb(MOD);
deque<int> q;
L[0] = n;
q.pb(0);
for(int i = 1; i < n; ++i){
while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
if(!q.empty()) L[i] = q.back();
else L[i] = n;
q.pb(i);
}
q.clear();
R[n-1] = n;
q.pb(n-1);
for(int i = n-2; i >= 0; --i){
while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
if(!q.empty()) R[i] = q.back();
else R[i] = n;
q.pb(i);
}
for(int i = 0; i < n; ++i) dp[i+1][0] = H[i];
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= n + 1; ++i){
dp[i][j] = max(dp[i][j - 1], dp[i+(1<<(j-1))][j-1]);
}
}
up[n][0][0] = n;
up[n][0][1] = n;
for(int i = 0; i < n; ++i){
if(H[L[i]] > H[R[i]]){
up[i][0][0] = L[i];
up[i][0][1] = R[i];
}else{
up[i][0][1] = L[i];
up[i][0][0] = R[i];
}
le[i][0] = L[i];
}
for(int j = 1; j < K; ++j){
for(int i = 0; i <= n; ++i){
up[i][j][0] = up[up[i][j - 1][0]][j - 1][0];
up[i][j][1] = up[up[i][j - 1][1]][j - 1][1];
le[i][j] = le[le[i][j - 1]][j - 1];
}
}
build(1, n, 1);
}
int minimum_jumps(int A, int B, int C, int D){
int v = -1, ans = 0;
int mx = maxx(C+1, D+1);
if(H[B] > H[C]) return -1;
v = B;
for(int j = K - 1; j >= 0; --j){
if(le[v][j] >= A && H[le[v][j]] < H[C]){
v = le[v][j];
}
}
for(int j = K - 1; j >= 0; --j){
if(v >= C && v <= D) return ans;
if(H[up[v][j][0]] <= mx){
ans += (1<<j);
v = up[v][j][0];
}
}
for(int j = K - 1; j >= 0; --j){
if(v >= C && v <= D) return ans;
if(H[up[v][j][1]] <= mx){
ans += (1<<j);
v = up[v][j][1];
}
}
if(v >= C && v <= D) return ans;
return -1;
}