| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 922010 | adhityamv | 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 <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int N=200000;
const int ln=20;
int INF=1000000000;
int leftjump[N];
int rightjump[N];
int h[N];
int n;
pii seg[2*N][ln];
int onlyr[2*N][ln];
void updateonlyr(int i,int val,int tp){
i+=n;
onlyr[i][tp]=val;
while(i>1){
onlyr[i<<1][tp]=max(onlyr[i][tp],onlyr[i^1][tp]);
i>>=1;
}
}
int queryonlyr(int l,int r,int tp){
r++;
l+=n;
r+=n;
int ans=-INF;
while(l<r){
if(l&1){
ans=max(ans,onlyr[l][tp]);
l++;
}
if(r&1){
ans=max(ans,onlyr[r-1][tp]);
r--;
}
l>>=1;
r>>=1;
}
return ans;
}
void update(int i,pii val,int tp){
i+=n;
seg[i][tp]=val;
while(i>1){
seg[i>>1][tp].first=min(seg[i][tp].first,seg[i^1][tp].first);
seg[i>>1][tp].second=max(seg[i][tp].second,seg[i^1][tp].second);
i>>=1;
}
}
pii query(int l,int r,int tp){
r++;
l+=n;
r+=n;
pii ans=mp(INF,-INF);
while(l<r){
if(l&1){
ans.first=min(ans.first,seg[l][tp].first);
ans.second=max(ans.second,seg[l][tp].second);
l++;
}
if(r&1){
ans.first=min(ans.first,seg[r-1][tp].first);
ans.second=max(ans.second,seg[r-1][tp].second);
r--;
}
l>>=1;
r>>=1;
}
return ans;
}
void init(int nn,vector<int> hh){
n=nn;
for(int i=0;i<n;i++) (h[i]=hh[i]);
stack<int> fl;
fl.push(-1);
for(int i=0;i<n;i++){
while(fl.top()!=-1 && h[fl.top()]<h[i]) fl.pop();
leftjump[i]=fl.top();
fl.push(i);
}
stack<int> fr;
fr.push(-1);
for(int i=n-1;i>=0;i--){
while(fr.top()!=-1 && h[fr.top()]<h[i]) fr.pop();
rightjump[i]=fr.top();
fr.push(i);
}
for(int i=0;i<n;i++){
if(rightjump[i]==-1) rightjump[i]=n;
}
for(int j=0;j<ln;j++) for(int i=0;i<2*n;i++) seg[i][j]=mp(INF,-INF);
for(int i=0;i<n;i++){
update(i,mp(leftjump[i],rightjump[i]),0);
}
//for(int i=0;i<2*n;i++) cout << seg[i][0].first << " " << seg[i][0].second << "\n";
for(int j=0;j<ln-1;j++){
for(int i=0;i<n;i++){
update(i,query(seg[i+n][j].first,seg[i+n][j].second,j),j+1);
}
}
for(int i=0;i<n;i++){
updateonlyr(i,rightjump[i],0);
}
for(int j=0;j<ln-1;j++){
for(int i=0;i<n;i++){
if(onlyr[i+n][j]==n) updateonlyr(i,n,j+1);
else updateonlyr(i,onlyr[onlyr[i+n][j]+n][j],j+1);
}
}
}
bool out(int n,pii p){
if(p.first<=n && n<=p.second) return false;
return true;
}
int cequalsd(int a,int b,int c){
int lb=leftjump[c];
if(lb==c) lb=-1;
if(b<=lb) return -1;
a=max(a,lb+1);
int cnt=0;
for(int j=ln-1;j>=0;j--){
auto p=query(a,b,j);
if(out(lb,p) && out(c,p)){
a=p.first;
b=p.second;
cnt+=(1<<j);
}
}
auto p=query(a,b,0);
if(!out(c,p)){
return cnt+1;
}
int bl=a;
int br=b;
while(bl!=br){
int bm=(bl+br)/2;
if(out(lb,query(a,bm,0))){
br=bm;
} else bl=bm+1;
}
a=bl;
for(int j=ln-1;j>=0;j--){
int nb=queryonlyr(a,b,j);
if(nb<c){
b=nb;
cnt+=(1<<j);
}
}
return cnt+1;
}
int minimum_jumps(int a,int b,int c,int d){
int ans=N;
for(int j=c;j<=d;j++){
int cans=cequalsd(a,b,j);
if(cans!=-1) ans=min(cans,ans);
}
if(ans==N) ans=-1;
return ans;
}