Submission #740959

#	Time	Username	Problem	Language	Result	Execution time	Memory
740959		tegid	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1710 ms	89492 KiB

jumps

#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],rev[200005];

struct node{
	int s,e,m,v;
	vector<int> dec;
	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]);
		}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);
		}
	}
	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);
	}
}*root;

int lrr[200005][20],rrr[200005][20];
int zoom[200005][20];

void init(int N, vector<int> H) {
	for(int i=0;i<N;i++){
		rev[H[i]]=i;
	}
	memset(lrr,-1,sizeof(lrr));
	memset(rrr,-1,sizeof(rrr));
	vector<ii> v;
	for(int i=0;i<N;i++){
		arr[i]=H[i];
		while(!v.empty()&&v.back().fi<H[i])v.pop_back();
		if(v.empty())lrr[i][0]=-1;
		else lrr[i][0]=v.back().se;
		v.pb(H[i],i);
	}
	v.clear();
	for(int i=N-1;i>=0;i--){
		while(!v.empty()&&v.back().fi<H[i])v.pop_back();
		if(v.empty())rrr[i][0]=-1;
		else rrr[i][0]=v.back().se;
		v.pb(H[i],i);
	}
	for(int i=0;i<N;i++){
		zoom[i][0]=(H[lrr[i][0]]>H[rrr[i][0]]?lrr[i][0]:rrr[i][0]);
	}
	root=new node(0,N-1);
	for(int i=1;i<20;i++){
		for(int j=0;j<N;j++){
			if(lrr[j][i-1]!=-1)lrr[j][i]=lrr[lrr[j][i-1]][i-1];
			else lrr[j][i]=-1;
			if(rrr[j][i-1]!=-1)rrr[j][i]=rrr[rrr[j][i-1]][i-1];
			else rrr[j][i]=-1;
			if(zoom[j][i-1]!=-1)zoom[j][i]=zoom[zoom[j][i-1]][i-1];
			else zoom[j][i]=-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;
	int idx=rev[start];
	int x1=idx,x2=idx;
	
	// from start, "alternate" between inc(B+1,C-1) and dec(0,A-1) until
		// reach midmax (then +1)
		// exceed midmax (+1 if you are <emax, impossible if >emax)
	int ans1=0;
	for(int i=19;i>=0;i--){
		if(zoom[x1][i]==-1)continue;
		if(arr[zoom[x1][i]]<=midmax){
			x1=zoom[x1][i];
			ans1+=(1<<i);
			//printf("%d %d\n",x1,ans1);
		}
	}
	if(arr[x1]!=midmax){
		ans1++;
	}
	int ans2=0;
	for(int i=19;i>=0;i--){
		if(zoom[x2][i]==-1)continue;
		if(arr[zoom[x2][i]]<emax){
			x2=zoom[x2][i];
			ans2+=(1<<i);
			//printf("%d %d\n",x2,ans2);
		}
	}
	return min(ans1,ans2)+1;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19