| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1346792 | goodpjw2008 | 밀림 점프 (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
#ifdef ONLINE_JUDGE
#include "jumps.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
using pii=pair<int,int>;
int h[200002],n,spr[200002][20],sph[200002][20],l[200002],r[200002];
pii spmx[200002][20];
pii rangemx(int l, int r){
int k=31-__builtin_clz(r-l+1);
return max(spmx[l][k],spmx[r-(1<<k)+1][k]);
}
void init(int N, vector<int> H){
n=N;
h[0]=1e9+1;
for(int i = 1; i <= n; i++){
h[i]=H[i-1];
spmx[i][0]={h[i],i};
}
for(int j = 1; j < 20; j++){
for(int i = 1; i+(1<<j)-1 <= n; i++){
spmx[i][j]=max(spmx[i][j-1],spmx[i+(1<<(j-1))][j-1]);
}
}
vector<int>stk;
stk.push_back(0);
for(int i = 1; i <= n; i++){
while(stk.size()>1&&h[stk.back()]<h[i])stk.pop_back();
l[i]=stk.back();
stk.push_back(i);
}
stk.clear();
stk.push_back(0);
for(int i = n; i >= 1; i--){
while(stk.size()>1&&h[stk.back()]<h[i])stk.pop_back();
r[i]=stk.back();
stk.push_back(i);
spr[i][0]=r[i];
if(l[i]&&r[i])sph[i][0]=(h[l[i]]>h[r[i]]?l[i]:r[i]);
else sph[i][0]=l[i]+r[i];
}
for(int j = 1; j < 20; j++){
for(int i = 1; i <= n; i++){
spr[i][j]=spr[spr[i][j-1]][j-1];
sph[i][j]=sph[sph[i][j-1]][j-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D){
A++;B++;C++;D++;
pii mx=rangemx(C,D);
if(B<C-1){
if(rangemx(B+1,C-1).x>mx.x)return -1;
}
int start,ll=1,rr=B;
while(ll<rr){
int m=(ll+rr)/2;
if(rangemx(m,B).x>mx.x)ll=m+1;
else rr=m;
}
start=max(rr,A);
if(start>B)return -1;
int cur=rangemx(start,B).y,ans=0;
for(int i = 19; i >= 0; i--){
if(sph[cur][i]<C&&h[sph[cur][i]]<=mx.x){
ans+=(1<<i);
cur=sph[cur][i];
}
}
if(spr[cur][0]>=C&&spr[cur][0]<=D)return ans+1;
else{
for(int i = 19; i >= 0; i--){
if(spr[cur][i]<C&&h[spr[cur][i]]<=mx.x){
ans+=(1<<i);
cur=spr[cur][i];
}
}
if(spr[cur][0]>=C&&spr[cur][0]<=D)return ans+1;
else return -1;
}
}