| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 549055 | zaneyu | 밀림 점프 (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*input
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/
#include "jumps.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int maxn=2e5+5;
#define sz(x) (int)x.size()
#define MNTO(x,y) x=min(x,(__typeof(x))y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
const int INF=0x3f3f3f3f;
vector<int> v[maxn];
int n;
int pv[maxn],nxt[maxn];
int l[maxn][20],r[maxn][20],mx[maxn][20];
void init(int N, vector<int> arr) {
n=N;
vector<int> st;
REP(i,n){
while(sz(st) and arr[st.back()]<arr[i]){
st.pop_back();
}
if(!sz(st)) pv[i]=-1;
else pv[i]=st.back();
st.pb(i);
}
st.clear();
for(int i=n-1;i>=0;i--){
while(sz(st) and arr[st.back()]<arr[i]){
st.pop_back();
}
if(!sz(st)) nxt[i]=-1;
else nxt[i]=st.back();
st.pb(i);
}
REP(i,n){
bool swp=0;
if(pv[i]==-1) mx[i][0]=nxt[i];
else if(nxt[i]==-1) mx[i][0]=pv[i];
else if(arr[nxt[i]]>arr[pv[i]]) mx[i][0]=nxt[i];
else mx[i][0]=pv[i];
l[i][0]=pv[i],r[i][0]=nxt[i];
}
REP1(j,18){
REP(i,n){
if(l[i][j-1]!=-1) l[i][j]=l[l[i][j-1]][j-1];
else l[i][j]=-1;
if(r[i][j-1]!=-1) r[i][j]=r[r[i][j-1]][j-1];
else r[i][j]=-1;
if(mx[i][j-1]!=-1) mx[i][j]=mx[mx[i][j-1]][j-1];
else mx[i][j]=-1;
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
int pos=B,ans=0;
for(int i=18;i>=0;i--){
if(l[pos][i]==-1) continue;
if(l[pos][i]>=A and nxt[l[pos][i]]<=D and nxt[l[pos][i]]!=-1) pos=l[pos][i];
}
for(int i=18;i>=0;i--){
if(mx[pos][i]==-1) continue;
if(nxt[mx[pos][i]]!=-1 and nxt[mx[pos][i]]<=D) ans+=(1<<i),pos=mx[pos][i];
}
for(int i=18;i>=0;i--){
if(r[pos][i]==-1) continue;
if(r[pos][i]<C) pos=r[pos][i],ans+=(1<<i);
}
if(r[pos][0]>D or r[pos][0]==-1) return -1;
return ans+1;
}
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}