| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 740896 | tegid | 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;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int arr[200005];
struct node{
int s,e,m,v;
vector<int> dec,inc;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;
if(s==e){
v=arr[s];
dec.pb(arr[s]);
inc.pb(arr[s]);
}else{
l=new node(s,m);
r=new node(m+1,e);
v=max(l->v,r->v);
dec=l->dec;
while(!dec.empty()&&dec.back()<r->dec[0])dec.pop_back()
for(int i:(r->dec))dec.pb(i);
inc=r->inc;
while(!inc.empty()&&inc.back()<l->inc[0])inc.pop_back();
for(int i:(l->inc))inc.pb(i);
}
}
int rmaxq(int x,int y){
if(x>y)return -1;
if(s>=x&&e<=y)return v;
if(y<=m)return l->rmaxq(x,y);
if(x>m)return r->rmaxq(x,y);
return max(l->rmaxq(x,y),r->rmaxq(x,y));
}
int sminq(int x,int y){
if(s>=x&&e<=y)return dec.back();
if(y<=m)return l->sminq(x,y);
return r->sminq(x,y);
}
int sdecq(int x,int y,int val){ // largest value in the dec array that is <val
if(s>=x&&e<=y)return *(--lower_bound(dec.rbegin(),dec.rend(),val));
if(y<=m)return l->sdecq(x,y,val);
if(x>m)return r->sdecq(x,y,val);
int lres=l->sdecq(x,y,val),rmax=r->rmaxq(x,y);
if(lres>rmax)return lres;
return r->sdecq(x,y,val);
}
ii sincq(int x,int y,int val){ // number of elements in the inc array that are >val
if(s>=x&&e<=y){
auto it=(upper_bound(inc.rbegin(),inc.rend(),val));
return mp(inc.rend()-it,*it);
}
if(y<=m)return l->sincq(x,y,val);
if(x>m)return r->sincq(x,y,val);
int rres=r->sincq(x,y,val),lmax=l->rmaxq(x,y);
if(rres.se>lmax)return rres;
ii lres=l->sincq(x,y,val);
lres.fi+=r->sincq(x,y,lmax).fi;
return lres;
}
}*root;
void init(int N, vector<int> H) {
for(int i=0;i<N;i++)arr[i]=H[i];
root=new node(0,N-1);
}
int minimum_jumps(int A, int B, int C, int D) {
int midmax=root->rmaxq(B+1,C-1),emax=root->rmaxq(C,D);
if(midmax>emax)return -1;
int smin=root->sminq(A,B);
if(smin>emax)return -1;
int start=root->sdecq(A,B,emax);
if(start>midmax)return 1;
return 1+root->sincq(B+1,C-1,start).fi;
}