Submission #946473

#	Time	Username	Problem	Language	Result	Execution time	Memory
946473		amirhoseinfar1385	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1501 ms	54064 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,lg=20;
int inf=1e9,kaf=(1<<19);
int n,all[maxn],fr[maxn],fl[maxn],sp[lg][maxn],spr[lg][maxn],mxsp[lg][maxn];

struct segmentmx{
	int seg[(1<<20)];
	void ins(int i,int w){
		i+=kaf;
		while(i>0){
			seg[i]=max(w,seg[i]);
			i>>=1;
		}
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}segmax;

void pre(){
	all[0]=all[n+1]=inf;
	vector<int>v;
	v.push_back(0);
	for(int i=1;i<=n;i++){
		segmax.ins(i,all[i]);
		while((int)v.size()>0&&all[v.back()]<=all[i]){
			v.pop_back();
		}
		fl[i]=v.back();
		v.push_back(i);
	}
	v.clear();
	v.push_back(n+1);
	for(int i=n;i>=1;i--){
		while((int)v.size()>0&&all[v.back()]<=all[i]){
			v.pop_back();
		}
		fr[i]=v.back();
		v.push_back(i);
		mxsp[0][i]=fr[i];
	}
	mxsp[0][n+1]=n+1;
	for(int i=1;i<=n;i++){
		spr[0][i]=fr[i];
		if(all[fr[i]]>=all[fl[i]]){
			sp[0][i]=fr[i];
		}else{
			sp[0][i]=fl[i];
		}
	}
	for(int i=1;i<lg;i++){
		for(int j=1;j<=n;j++){
			sp[i][j]=sp[i-1][sp[i-1][j]];
			spr[i][j]=spr[i-1][spr[i-1][j]];
			mxsp[i][j]=max(mxsp[i-1][j],mxsp[i-1][sp[i-1][j]]);
		}
	}
}

void init(int N,vector<int> H) {
	n=N;
	for(int i=1;i<=n;i++){
		all[i]=H[i-1];
	}
	pre();
}

int cal(int a,int b,int c,int mx){
	if(all[a]>=mx){
		return inf;
	}
	int ret=0;
	for(int i=lg-1;i>=0;i--){
		if(sp[i][a]!=0&&all[sp[i][a]]<mx&&mxsp[i][a]<b){
			ret+=(1<<i);
			a=sp[i][a];
			if(a>=b&&a<=c){
				return ret;
			}
		}
	}
	for(int i=lg-1;i>=0;i--){
		if(spr[i][a]!=0&&spr[i][a]<b){
			a=spr[i][a];
			ret+=(1<<i);
		}
	}
	if(all[a]>=mx){
		return inf;
	}
	return ret+1;
}

int solve(int a,int b,int c,int d){
	int mxb=segmax.pors(1,0,kaf-1,c,d);
	int low=a-1,high=b,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(segmax.pors(1,0,kaf-1,mid,b)<mxb){
			high=mid;
		}else{
			low=mid;
		}
	}
	int z=segmax.pors(1,0,kaf-1,high,b);
	low=a,high=b+1;
	while(high-low>1){
		mid=(high+low)>>1;
		if(segmax.pors(1,0,kaf-1,mid,b)>=z){
			low=mid;	
		}else{
			high=mid;
		}
	}
	/*int wh=b,mx=all[b];
	for(int i=b-1;i>=a;i--){
		if(all[i]>=mxb){
			break;
		}
		if(all[i]>mx){
			mx=all[i];
			wh=i;
		}
	}*/
	int res=cal(low,c,d,mxb);
	if(res>=inf){
		res=-1;
	}
	return res;
}

int minimum_jumps(int A, int B, int C, int D) {
 	A++;
 	B++;
 	C++;
 	D++;
 	return solve(A,B,C,D);
}

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