| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1277610 | hainam2k9 | 밀림 점프 (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
#include "jumps.h"
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,a[MAXN],stmax[20][MAXN];
int L[MAXN],R[MAXN],jump[20][MAXN],jump2[20][MAXN];
void build(){
for(int i = 1; i<=n; ++i)
stmax[0][i]=i;
for(int i = 1; i<=__lg(n); ++i)
for(int j = 1; j+(1<<i)-1<=n; ++j)
stmax[i][j]=(a[stmax[i-1][j]]>=a[stmax[i-1][j+(1<<(i-1))]] ? stmax[i-1][j] : stmax[i-1][j+(1<<(i-1))]);
stack<int> st;
for(int i = 1; i<=n; ++i){
while(!st.empty()&&a[i]>=a[st.top()]) st.pop();
L[i]=(st.empty() ? i : st.top());
st.ins(i);
}
while(!st.empty()) st.pop();
for(int i = n; i>0; --i){
while(!st.empty()&&a[i]>=a[st.top()]) st.pop();
R[i]=(st.empty() ? i : st.top());
st.ins(i);
}
for(int i = 1; i<=n; ++i){
if(a[L[i]]>a[R[i]]) jump[0][i]=L[i], jump2[0][i]=R[i];
else jump[0][i]=R[i], jump2[0][i]=L[i];
}
for(int i = 1; i<=__lg(n); ++i)
for(int j = 1; j<=n; ++j)
jump[i][j]=jump[i-1][jump[i-1][j]], jump2[i][j]=jump2[i-1][jump2[i-1][j]];
}
int getmax(int l, int r){
int k=__lg(r-l+1);
return (a[stmax[k][l]]>=a[stmax[k][r-(1<<k)+1]] ? stmax[k][l] : stmax[k][r-(1<<k)+1]);
}
int bs(int l, int r, int x){
int rs=-1, R=r;
while(l<=r){
int mid=(l+r)>>1;
if(a[getmax(mid,r)]<=x) rs=getmax(mid,R), r=mid-1;
else l=mid+1;
}
return rs;
}
void init(int N, vector<int> v){
n=N;
for(int i = 1; i<=n; ++i)
a[i]=v[i-1];
build();
}
int minimum_jumps(int l, int r, int u, int v){
++l, ++r, ++u, ++v;
if(r+1==u){
if(a[r]<a[getmax(u,v)]) return 1;
return 0;
}
int MAX=getmax(r+1,u-1),x=bs(l,r,a[MAX]),cnt=0;
if(x!=-1&&a[MAX]<a[getmax(u,v)]){
for(int i = __lg(n); i>=0; --i)
if(a[jump[i][x]]<=a[MAX]) x=jump[i][x], cnt+=1<<i;
for(int i = __lg(n); i>=0; --i)
if(a[jump2[i][x]]<a[MAX]) x=jump2[i][x], cnt+=1<<i;
if(a[x]>=a[MAX]) rs=min(rs,cnt+1);
else if(a[jump2[0][x]]>=a[MAX]) ++cnt, rs=min(rs,cnt+1);
}
if(L[MAX]!=MAX&&a[L[MAX]]<a[getmax(u,v)]){
MAX=L[MAX], x=getmax(l,r), cnt=0;
if(l<=MAX&&MAX<=r) rs=1;
else{
for(int i = __lg(n); i>=0; --i)
if(a[jump[i][x]]<=a[MAX]) x=jump[i][x], cnt+=1<<i;
for(int i = __lg(n); i>=0; --i)
if(a[jump2[i][x]]<a[MAX]) x=jump2[i][x], cnt+=1<<i;
if(a[x]>=a[MAX]) rs=min(rs,cnt+1);
else if(a[jump2[0][x]]>=a[MAX]) ++cnt, rs=min(rs,cnt+1);
}
}
return (rs<1e9 ? rs : -1);
}
//int main()
//{
// tt;
// if(fopen((NAME + ".INP").c_str(), "r")) fo;
//}