| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 501369 | AdamAmanbaev | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
#define rep(i, a, b) for(ll i=a; i<b; i++)
#define repd(i, a, b) for(ll i=a; i>=b; i--)
int n, h[int(2e5+10)];
int jmp_l[int(2e5+10)][30];
int jmp_r[int(2e5+10)][30];
void init(int N, int H[]) {
n=N+2;
h[0]=1e8;
rep(i, 0, N)
h[i+1]=H[i];
h[n-1]=1e8;
stack<int> st;
rep(i, 0, n) {
while(sz(st) && h[st.top()]<h[i])
jmp_r[st.top()][0]=i, st.pop();
st.push(i);
}
while(sz(st))
st.pop();
repd(i, n-1, 0) {
while(sz(st) && h[st.top()]<h[i])
jmp_l[st.top()][0]=i, st.pop();
st.push(i);
}
rep(i, 1, 30)
rep(k, 0, n) {
jmp_l[k][i]=jmp_l[jmp_l[k][i-1]][i-1];
jmp_r[k][i]=jmp_r[jmp_r[k][i-1]][i-1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
if(B+1==C) {
if(jmp_r[B][0]>D)
return -1;
else
return 1;
}
int ind=B+1;
repd(i, 29, 0)
if(jmp_r[ind][i]<C)
ind=jmp_r[ind][i];
if(jmp_r[ind][0]>D)
return -1;
if(h[B]>h[ind]) {
if(jmp_r[B][0]>D)
return -1;
else
return 1;
}
int cur=B;
repd(i, 29, 0)
if(h[jmp_l[cur][i]]<h[ind] && jmp_l[cur][i]>=A)
cur=jmp_l[cur][i];
ll ans=0;
if(jmp_l[cur][0]>=A) {
if(jmp_r[jmp_l[cur][0]][0]<=D)
return 1;
}
else {
repd(i, 29, 0)
if(h[jmp_l[cur][i]]>h[jmp_r[cur][i]] && h[jmp_l[cur][i]]<=h[ind]) {
ans|=(1<<i);
cur=jmp_l[cur][i];
}
else if(h[jmp_r[cur][i]]>=h[jmp_l[cur][i]] && h[jmp_l[cur][i]]<=h[ind]) {
ans|=(1<<i);
cur=jmp_r[cur][i];
}
if(h[cur]==h[ind])
return ans+1;
if(jmp_l[cur][0] && jmp_r[jmp_l[cur][0]][0]<=D)
return ans+2;
}
repd(i, 29, 0)
if(jmp_r[cur][i]<C) {
cur=jmp_r[cur][i];
ans+=1<<i;
}
if(jmp_r[cur][0]>=C && jmp_r[cur][0]<=D)
return ans+1;
else
return -1;
}