| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 569516 | S2speed | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16;
ll gcd(ll a , ll b){
if(a < b) swap(a , b);
if(b == 0) return a;
return gcd(b , a % b);
}
inline ll tav(ll n , ll k){
ll res = 1;
while(k > 0){
if(k & 1){
res *= n; res %= md;
}
n *= n; n %= md;
k >>= 1;
}
return res;
}
struct segtree {
int sz = 1;
vector<int> val;
void init(int n){
while(sz < n) sz <<= 1;
val.assign(sz << 1 , 0);
return;
}
void build(vector<int> &a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < sze(a)){
val[x] = a[lx];
}
return;
}
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
build(a , ln , lx , m); build(a , rn , m , rx);
val[x] = max(val[ln] , val[rn]);
return;
}
void build(vector<int> &a){
build(a , 0 , 0 , sz);
return;
}
void set(int i , int k , int x , int lx , int rx){
if(rx - lx == 1){
val[x] = k;
return;
}
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
if(i < m){
set(i , k , ln , lx , m);
} else {
set(i , k , rn , m , rx);
}
val[x] = max(val[ln] , val[rn]);
return;
}
void set(int i , int k){
set(i , k , 0 , 0 , sz);
return;
}
int cal(int l , int r , int x , int lx , int rx){
if(rx <= l || lx >= r) return 0;
if(rx <= r && lx >= l) return val[x];
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
int a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
return max(a , b);
}
int cal(int l , int r){
return cal(l , r , 0 , 0 , sz);
}
void clear(){
sz = 1;
val.clear();
return;
}
};
int n;
segtree st;
vector<int> a , v;
int lf[maxn] , rt[maxn] , jal[maxn][20] , jar[maxn][20] , jan[maxn][20] , jax[maxn][20];
vector<pii> u;
int p[maxn];
void init(int N, vector<int> H){
memset(jal , -1 , sizeof(jal));
memset(jar , -1 , sizeof(jar));
memset(jan , -1 , sizeof(jan));
memset(jax , -1 , sizeof(jax));
a = H;
n = N;
for(int i = 0 ; i < n ; i++){
p[a[i]] = i;
}
for(int i = 0 ; i < n ; i++){
int h = -1;
while(!v.empty()){
int j = v.back();
if(a[j] > a[i]){
h = j;
break;
}
v.pop_back();
}
lf[i] = h;
v.push_back(i);
}
v.clear();
for(int i = n - 1 ; ~i ; i--){
int h = -1;
while(!v.empty()){
int j = v.back();
if(a[j] > a[i]){
h = j;
break;
}
v.pop_back();
}
rt[i] = h;
v.push_back(i);
}
for(int i = 0 ; i < n ; i++){
jal[i][0] = lf[i];
for(int j = 1 ; j < 20 ; j++){
if(jal[i][j - 1] == -1) break;
jal[i][j] = jal[jal[i][j - 1]][j - 1];
}
}
for(int i = n - 1 ; ~i ; i--){
jar[i][0] = rt[i];
for(int j = 1 ; j < 20 ; j++){
if(jar[i][j - 1] == -1) break;
jar[i][j] = jar[jar[i][j - 1]][j - 1];
}
}
for(int i = 0 ; i < n ; i++){
u.push_back({a[i] , i});
}
sort(all(u) , greater<pii>());
for(int e = 1 ; e < n ; e++){
int i = u[e].second;
if(lf[i] == -1){
jax[i][0] = rt[i];
} else if(rt[i] == -1){
jax[i][0] = lf[i];
} else {
if(a[lf[i]] > a[rt[i]]){
jax[i][0] = lf[i];
jan[i][0] = rt[i];
} else {
jax[i][0] = rt[i];
jan[i][0] = lf[i];
}
}
for(int j = 1 ; j < 20 ; j++){
if(jax[i][j - 1] == -1) break;
jax[i][j] = jax[jax[i][j - 1]][j - 1];
}
for(int j = 1 ; j < 20 ; j++){
if(jan[i][j - 1] == -1) break;
jan[i][j] = jan[jan[i][j - 1]][j - 1];
}
}
st.init(n);
st.build(a);
return;
}
int dis(int x , int y){
int res = 0;
for(int j = 19 ; ~j ; j--){
int h = jax[x][j];
if(h == -1) continue;
if(a[h] > a[y]) continue;
res += (1 << j);
x = h;
}
for(int j = 19 ; ~j ; j--){
int h = jan[x][j];
if(h == -1) continue;
if(a[h] > a[y]) continue;
res += (1 << j);
x = h;
}
return (x == y ? res : -2);
}
int minimum_jumps(int l1, int r1, int l2, int r2){
r1++; r2++;
if(r1 == l1){
if(rt[r1 - 1] == -1 || rt[r1 - 1] >= r2) return -1;
return 1;
}
int d = st.cal(r1 , l2) , k = st.cal(l2 , r2);
if(d > k) return -1;
if(a[r1 - 1] > d){
if(a[r1 - 1] > k) return -1;
return 1;
}
int v = r1 - 1;
for(int j = 19 ; ~j ; j--){
int h = jal[v][j];
if(h < l1) continue;
if(a[h] > d) continue;
v = h;
}
int res = dis(v , p[d]) + 1;
if(lf[v] >= l1) return 1;
int o = v;
for(int j = 19 ; ~j ; j--){
int h = jal[o][j];
if(h == -1) continue;
if(a[h] > d) continue;
o = h;
}
o = lf[o];
if(o == -1) return res;
if(a[o] > k) return res;
ll h = dis(v , o);
if(h != -2){
res = min(res , h + 1);
if(res == -1) res = h + 1;
}
return res;
}