| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1052595 | Piokemon | Rainforest Jumps (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 2e5;
constexpr int K = 18;
int jmp[N+9][K+1];
int last[N+9][K+1];
int h[N+9];
int l[N+9];
int r[N+9];
int dst[N+9];
int n;
constexpr int base = (1<<18);
pair<int,int> tree[2*base+9];
// min
pair<int,int> bet(pair<int,int> a, pair<int,int> b){
if (a.first>b.first)return a;
else return b;
}
pair<int,int> query(int x, int a, int b, int p, int k){
if (b<p || k<a)return {-1,0};
if (p<=a && b<=k){
return tree[x];
}
int mid=(a+b)/2;
return bet(query(2*x,a,mid,p,k),query(2*x+1,mid+1,b,p,k));
}
void init(int N, std::vector<int> H) {
n=N;
for (int x=0;x<n;x++)h[x]=H[x];
vector<pair<int,int>> stos; stos.push_back({2e9,n});
for (int x=0;x<n;x++){
while(h[x]>stos.back().first)stos.pop_back();
l[x]=stos.back().second;
stos.push_back({h[x],x});
}
h[n]=-2e9;
stos.clear(); stos.push_back({2e9,n});
for (int x=n-1;x>=0;x--){
while(h[x]>stos.back().first)stos.pop_back();
r[x]=stos.back().second;
stos.push_back({h[x],x});
}
for (int x=base;x<base+n;x++)tree[x]={h[x-base],x-base};
for (int x=base-1;x>=1;x--)tree[x]=bet(tree[2*x],tree[2*x+1]);
for (int x=0;x<n;x++){
if (h[l[x]]>h[r[x]])jmp[x][0]=l[x];
else jmp[x][0]=r[x];
last[x][0]=max(x,jmp[x][0]);
}
jmp[n][0]=n; last[n][0]=n;
for (int k=1;k<=K;k++){
for (int x=0;x<=n;x++){
jmp[x][k]=jmp[jmp[x][k-1]][k-1];
last[x][k]=max(last[x][k-1],last[jmp[x][k-1]][k-1]);
}
}
/*for (int x=0;x<n;x++){
cerr << l[x] << ' ' << r[x] << '\n';
}*/
return;
}
int minimum_jumps(int A, int B, int C, int D){
if (C<=B && B<=D)return 0;
if (C<=A && A<=D)return 0;
if (A<=C && D<=B)return 0;
int mid=0;
if (C-B>1)mid=query(1,0,base-1,B+1,C-1);
if (A-D>1)mid=query(1,0,base-1,D+1,A-1);
int pocz= A; // TODO
int odp=0;
for (int k=K;k>=0;k--){
if (last[pocz][k]<C){
odp+=(1<<k);
pocz=jmp[pocz][k];
}
}
while ((!(C<=pocz && pocz <= D)) && pocz!=n){
pocz=jmp[pocz][0];
odp++;
}
if (C<=pocz && pocz<=D) return odp;
else return -1;
}