| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1310431 | namhh | Rainforest Jumps (APIO21_jumps) | C++20 | 0 ms | 0 KiB |
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 200005;
const int lg = 18;
int st1[N][lg],st2[N][lg],dp[N][lg];
void init(int n, vector<int>h){
stack<int>s;
for(int i = n; i >= 1; i--){
while(s.size() && h[s.top()] <= h[i-1]) s.pop();
if(s.size()) st2[i][0] = s.top();
s.push(i-1);
}
while(s.size()) s.pop();
for(int i = 1; i <= n; i++){
while(s.size() && h[s.top()] <= h[i-1]) s.pop();
if(s.size()) st1[i][0] = s.top();
s.push(i-1);
}
for(int i = 1; i <= n; i++){
if(h[st1[i][0]] > h[st2[i][0]]) dp[i][0] = st1[i][0];
else dp[i][0] = st2[i][0];
}
for(int j = 1; j < lg; j++){
for(int i = 1; i <= n; i++){
st1[i][j] = st1[st1[i][j-1]][j-1];
st2[i][j] = st2[st2[i][j-1]][j-1];
dp[i][j] = dp[dp[i][j-1]][j-1];
}
}
}
int minimum_jump(int A, int B, int C, int D){
int u = B;
for(int i = lg-1; i >= 0; i--){
if(st1[u][i] >= A && st2[st1[u][i]][0] <= D) u = st1[u][i];
}
int ans = 0;
for(int i = lg-1; i >= 0; i--){
if(dp[u][i] < C){
ans += (1 << i);
u = dp[u][i];
}
}
for(int i = lg-1; i >= 0; i--){
if(st2[u][i] < C){
u = st2[u][i];
ans += (1 << i);
}
}
if(st2[u][0] < C || st2[u][0] > D) return -1;
return ans+1;
}