#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]
#define lsb(x) ((x)&(-(x)))
//const int INF = 2147483647;
//const int LNF = INF*INF;
const int INF = 1000000007;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int MAX = 200010;
const int lgMAX = 20;
int n;
int h[MAX];
int edge_l[MAX], edge_r[MAX];
int anc_l[MAX][lgMAX];
int anc_hi[MAX][lgMAX], anc_lo[MAX][lgMAX];
int Max[MAX][lgMAX];
int dest_Max;
int query_Max(int L, int R){ /// [L, R]
int len = R - L + 1;
int lglen = __lg(len);
return max(Max[L][lglen], Max[R - (1<<lglen) + 1][lglen]);
}
int get_start(int A, int B){
int ret = B;
for(int j=lgMAX-1; j>=0; j--){
if( anc_l[ret][j] != INF and h[anc_l[ret][j]] < dest_Max and anc_l[ret][j] >= A ){
ret = anc_l[ret][j];
}
}
return ret;
}
pii jump_hi(int v){
int ret = 0;
for(int j=lgMAX-1; j>=0; j--){
if( anc_hi[v][j] != INF and h[anc_hi[v][j]] <= dest_Max ){
v = anc_hi[v][j];
ret += (1<<j);
}
}
return mkp(v, ret);
}
int jump_lo(int v){
int ret = 0;
for(int j=lgMAX-1; j>=0; j--){
if( anc_lo[v][j] != INF and h[anc_lo[v][j]] <= dest_Max ){
v = anc_lo[v][j];
ret += (1<<j);
}
}
if( h[v] < dest_Max and ( anc_lo[v][0] == INF or h[anc_lo[v][0]] > dest_Max ) ){
ret = INF;
}
return ret;
}
void init(int N, vi H){
/// input
n = N;
FOR(i, 0, n-1, 1){
h[i] = H[i];
}
/// monotonic stack
FOR(i, 0, n-1, 1){
edge_l[i] = INF; /// INF -> no edge
edge_r[i] = INF;
}
vi stk;
FOR(i, 0, n-1, 1){
while(!stk.empty() and h[stk.back()] < h[i]){
stk.pop_back();
}
if(!stk.empty()){
edge_l[i] = stk.back();
}
stk.pb(i);
}
stk.clear();
for(int i=n-1; i>=0; i--){
while(!stk.empty() and h[stk.back()] < h[i]){
stk.pop_back();
}
if(!stk.empty()){
edge_r[i] = stk.back();
}
stk.pb(i);
}
/// 2^k-th ancestor
FOR(i, 0, n-1, 1){
if(edge_l[i]==INF and edge_r[i]==INF){
anc_hi[i][0] = INF;
anc_lo[i][0] = INF;
}
else if(edge_l[i]==INF or edge_r[i]==INF){
anc_hi[i][0] = INF;
anc_lo[i][0] = min(edge_l[i], edge_r[i]);
}
else{
anc_hi[i][0] = (h[edge_l[i]] > h[edge_r[i]]) ? edge_l[i] : edge_r[i];
anc_lo[i][0] = (h[edge_l[i]] < h[edge_r[i]]) ? edge_l[i] : edge_r[i];
}
anc_l [i][0] = edge_l[i];
}
FOR(j, 1, lgMAX-1, 1){
FOR(i, 0, n-1, 1){
anc_hi[i][j] = (anc_hi[i][j-1]!=INF) ? anc_hi[ anc_hi[i][j-1] ][j-1] : INF;
anc_lo[i][j] = (anc_lo[i][j-1]!=INF) ? anc_lo[ anc_lo[i][j-1] ][j-1] : INF;
anc_l [i][j] = (anc_l [i][j-1]!=INF) ? anc_l [ anc_l [i][j-1] ][j-1] : INF;
}
}
/// sparse table for Max query
FOR(i, 0, n-1, 1){
Max[i][0] = h[i];
}
FOR(j, 1, lgMAX-1, 1){
FOR(i, 0, n-1, 1){
if(i + (1<<j-1) <= n-1){
Max[i][j] = max(Max[i][j-1], Max[i + (1<<j-1)][j-1]);
}
else{
Max[i][j] = Max[i][j-1];
}
}
}
}
int minimum_jumps(int A, int B, int C, int D){
dest_Max = query_Max(C, D);
int start = get_start(A, B);
int v = start, res;
pii tmp = jump_hi(start);
v = tmp.F;
res = tmp.S;
res += jump_lo(v);
if(res < INF){
return res;
}
else{
return -1;
}
}
/*
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init(7, {3, 2, 1, 6, 4, 5, 7});
cerr<<minimum_jumps(0, 2, 4, 6)<<endl; /// 2
cerr<<minimum_jumps(0, 0, 6, 6)<<endl; /// 2
cerr<<minimum_jumps(0, 2, 5, 5)<<endl; /// -1
return 0;
}
*/
Compilation message
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:161:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
161 | if(i + (1<<j-1) <= n-1){
| ~^~
jumps.cpp:162:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
162 | Max[i][j] = max(Max[i][j-1], Max[i + (1<<j-1)][j-1]);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Incorrect |
244 ms |
53940 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Incorrect |
244 ms |
53940 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
