| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278893 | huyngodzz | 밀림 점프 (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
///huynhocute123///
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = b; i >= a; --i)
#define ALL(v) v.begin(),v.end()
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
//random_device rd;
//mt19937 rng(rd());
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
const int MAX = 1e9+9;
const long long MAXLL = 1e18+9;
const double pi = 3.14159265358979323846;
const double rad = 3.14159265358979323846 /180;
bool minimize(int &u, int v){
if(v < u){
u = v;
return 1;
}
return 0;
}
bool maximize(int &u, int v){
if(v > u){
u = v;
return 1;
}
return 0;
}
bool maximizell(long long &u, long long v){
if(v > u){
u = v;
return 1;
}
return 0;
}
bool minimizell(long long &u, long long v){
if(v < u){
u = v;
return 1;
}
return 0;
}
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
if(n == 0) return 1;
int t = fastPow(a, n >> 1);
t = 1ll * t * t % mod;
if(n & 1) t = 1ll * t * a % mod;
return t;
}
inline void Add(int& x ,int y){
x += y;
if(x >= mod)x -=mod;
}
inline void Sub(int& x, int y){
x-= y;
if(x < 0)x += mod;
}
const int maxN = 2 * 1e5 + 999 ;
int n , h[maxN], m, L[maxN][20] , R[maxN][20] , best[maxN][20];
int calc(int u , int v){
if(h[u] > h[v])return u;
return v ;
}
pii st[4 *maxN];
void build(int id ,int l ,int r){
if(l == r){
st[id] = {h[l] , l};
return;
}
int mid = (l + r)/2;
build(id << 1 , l, mid);
build(id << 1 | 1,mid + 1 , r);
if(st[id << 1] > st[id << 1 | 1])st[id] = st[id << 1];
else st[id ]= st[id << 1 | 1];
}
pii get(int id ,int l, int r ,int u ,int v){
if(v < l || u > r)return {0 , 0};
if(u <= l && r <= v)return st[id];
int mid = (l + r)/2;
pii T1 =get(id << 1 , l ,mid , u ,v);
pii T2 = get(id << 1 | 1 ,mid + 1, r, u , v);
if(T1.F > T2.F)return T1;
else return T2;
}
int minimum_jumps(int A , int B ,int C ,int D){
A++;
B++;
C++;
D++;
if(B + 1 == C){
if(R[B][0] >= 1 && R[B][0] <= D)return 1;
else return -1;
}
int mx_mid = get(1 , 1, n, B + 1, C - 1).S;
int NewB = B;
REP(i, 0 , 18){
if(A <= L[NewB][i] && L[NewB][i] <= n && h[L[NewB][i]] <= h[mx_mid])NewB = L[NewB][i];
}
// cerr << mx_mid;
// cerr << NewB << '\n';
if(h[NewB] > h[mx_mid]){
if(R[NewB][0] >= 1 && R[NewB][0] <= D)return 1;
else return -1;
}
// cerr << "SD";
/// h[newB] < h[mx_mid]
if(A <= L[NewB][0] && L[NewB][0] <= n){
if(A <= R[L[NewB][0]][0] && R[L[NewB][0]][0] <= D)return 1;
}
/// .o. 111 kkk
int ans = 0;
REP(i, 0 , 18){
if(1 <= best[NewB][i] && best[NewB][i] <= n && h[best[NewB][i]] < h[mx_mid]){
NewB = best[NewB][i];
ans += (1 << i);
// cerr << "XC";
}
}
if(1 <= L[NewB][0] && L[NewB][0] <= n){
if(C <=R[L[NewB][0]][0] && R[L[NewB][0]][0] <= D)return ans + 2;
}
REP(i, 0 , 18){
if(1 <= R[NewB][i] && R[NewB][i] <= n && h[R[NewB][i]] < h[mx_mid]){
NewB = R[NewB][i];
ans += (1 << i);
// cerr << "XC";
}
}
// cerr << NewB << " ";
// cerr << "ASD";
// cerr << ans << " ";
if( C<= R[mx_mid][0]&&R[mx_mid][0] <= D){
return ans + 2;
}else return -1;
// cout << mx_mid << '\n';
return 0;
}
void init(int N ,int[] H){
n = N;
FOR(i, 1, n)h[i] = H[i - 1];
stack<int>stk;
build(1, 1, n);
FOR(i, 1, n){
while(stk.size() && h[stk.top()] <= h[i])stk.pop();
if(stk.size())L[i][0] = stk.top();
else L[i][0] = 0;
stk.push(i);
}
// h[0] = MAX;
while(stk.size())stk.pop();
REP(i, 1, n){
while(stk.size() && h[stk.top()] <= h[i])stk.pop();
if(stk.size())R[i][0] = stk.top();
else R[i][0] = 0;
stk.push(i);
}
FOR(i, 1, n){
best[i][0] = calc(L[i][0] , R[i][0]);
// cout << L[i] << " " << best[i][0] << " " << R[i] << '\n';
// cout << i << " " << best[i][0] << '\n';
}
FOR(i, 1, 18){
FOR(u, 1, n){
best[u][i] = best[best[u][i - 1]][i - 1];
L[u][i] = L[L[u][i - 1]][i - 1];
R[u][i] = R[R[u][i - 1]][i - 1];
}
}
}