Submission #412595

#	Time	Username	Problem	Language	Result	Execution time	Memory
412595		kshitij_sodani	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1730 ms	58404 KiB

jumps

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


#include "jumps.h"

#include <vector>
int n;
int it[200001];
vector<int> adj[200001];
int ne[200001];
int par[200001][20];
int par2[200001][20];
int par3[200001][20];

int le[200001];
int re[200001];


void init(int nn, std::vector<int> aa) {
	n=nn;
	for(int i=0;i<n;i++){
		it[i]=aa[i];
		it[i]--;
		ne[i]=-1;
	}
	//build(0,0,n-1);
	vector<pair<int,int>> ss;
	for(int i=0;i<n;i++){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			/*if(abs(it[i]-ss.back().b)>1){
				ne[it[i]]=ss.back().a;

			}*/
			le[i]=ss.back().b;
			//adj[i].pb(ss.back().b);
		}
		else{
			le[i]=-1;
		}
		ss.pb({it[i],i});
	}
	ss.clear();
	for(int i=n-1;i>=0;i--){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			/*if(abs(it[i]-ss.back().b)>1){
				ne[it[i]]=ss.back().a;

			}*/
			re[i]=ss.back().b;
			//adj[i].pb(ss.back().b);
		}
		else{
			re[i]=-1;
		}
		ss.pb({it[i],i});
	}
	for(int i=0;i<n;i++){
		if(le[i]==-1 and re[i]==-1){
			ne[i]=-1;
		}
		else if(le[i]==-1){
			ne[i]=re[i];
		}
		else if(re[i]==-1){
			ne[i]=le[i];

		}
		else{
			pair<int,int> ma2={it[le[i]],le[i]};
			pair<int,int> ma3={it[re[i]],re[i]};
			ma2=max(ma2,ma3);
			ne[i]=ma2.b;
		}
		par[i][0]=ne[i];
		par2[i][0]=re[i];
		par3[i][0]=le[i];
		//cout<<ne[i]<<",";
	}
	//cout<<endl;
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par2[i][j-1]==-1){
				par2[i][j]=-1;
			}
			else{
				par2[i][j]=par2[par2[i][j-1]][j-1];
			}
		}
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par3[i][j-1]==-1){
				par3[i][j]=-1;
			}
			else{
				par3[i][j]=par3[par3[i][j-1]][j-1];
			}
		}
	}
}

int dist[200001];
int minimum_jumps(int aa, int bb, int cc, int dd) {
	/*if(n>2000){
		return cc-bb;
	}
*/

	int ff=cc;
	for(int j=19;j>=0;j--){
		if(par2[ff][j]==-1){
			continue;
		}
		if(par2[ff][j]<=dd){
			ff=par2[ff][j];
		}
	}
	int ee=bb;
		for(int j=19;j>=0;j--){
			if(par3[ee][j]==-1){
				continue;
			}
			/*if(aa==cc){
				break;
			}*/
			if(par3[ee][j]>=aa and it[par3[ee][j]]<=it[ff]){
				//co+=(1<<j);
				ee=par3[ee][j];
			}
		}
		aa=ee;
		bb=ee;
		int gg=bb;
	for(int j=19;j>=0;j--){
			if(par2[gg][j]==-1){
				continue;
			}
			/*if(bb==cc){
				break;
			}*/
			if(par2[gg][j]<cc){
				//co+=(1<<j);
				gg=par2[gg][j];
			}
		}
		gg=par2[gg][0];
		if(gg<cc or gg>dd){
			return -1;
		}
		cc=gg;
		int ans=0;
		dd=ff;
		gg=bb;
		for(int j=19;j>=0;j--){
			if(par[gg][j]==-1){
				continue;
			}
			if(it[par[gg][j]]<it[cc]){
				gg=par[gg][j];
				ans+=(1<<j);
			}
		}
		int ans2=0;
		int hh=gg;
		for(int j=19;j>=0;j--){
			if(par2[gg][j]==-1){
				continue;
			}
			/*if(gg>=cc and gg<=dd){
				break;
			}*/
			if(par2[gg][j]<cc){
				gg=par2[gg][j];
				ans2+=(1<<j);
			}
		}
		ans2+=1;
		int fin=ans+ans2;
		if(le[hh]>=0){
			if(it[le[hh]]<=it[dd]){
				fin=min(fin,ans+2);
			}
		}
		return fin;
		while(gg<cc or gg>dd){
			ans++;
			if(par2[gg][0]>=cc and par2[gg][0]<=dd){
				break;
			}
			if(par[gg][0]>=0 and it[par[gg][0]]<=it[dd]){
				gg=par[gg][0];
				continue;
			}
			gg=par2[gg][0];
		}
		return ans;

	//if(aa==bb and cc==dd){
		/*if(it[aa]>it[cc]){
			return -1;
		}*/
		//int co=0;
		int co=0;
		for(int j=19;j>=0;j--){
			if(par[aa][j]==-1){
				continue;
			}
			if(it[par[aa][j]]<=it[cc]){
				co+=(1<<j);
				aa=par[aa][j];
			}
		}
		for(int j=19;j>=0;j--){
			if(par2[aa][j]==-1){
				continue;
			}
			if(aa==cc){
				break;
			}
			if(par2[aa][j]<=cc){
				co+=(1<<j);
				aa=par2[aa][j];
			}
		}
	
		return co;
	//}
	/*	if(aa!=cc){
			co++;
		}

		while(aa!=cc){
			co++;
			if(le[aa]==-1){

				aa=re[aa];
				continue;
			}
			if(re[aa]==-1){
				aa=le[aa];
				continue;
			}
			if(it[re[aa]]<=cc and it[le[aa]]<=cc){

			}
			else if(it[re[aa]]<=cc){

			}
			else if(it[le[aa]]>=cc)

		}

	}
*/



/*	if(it[aa]>it[cc]){
		return -1;
	}
	aa=it[aa];
	cc=it[cc];

	int co=0;
	for(int j=19;j>=0;j--){
		if(par[aa][j]==-1){
			continue;
		}
		if(par[aa][j]<=cc){
			co+=(1<<j);
			aa=par[aa][j];
		}
	}
	return co;
	while(aa!=cc){
		co++;
		if(ne[aa]>=0){
			if(ne[aa]<=cc){
				aa=ne[aa];
				continue;
			}
		}
		aa++;
		continue;
	}*/
/*	for(int i=0;i<n;i++){
		dist[i]=-1;
	}
	queue<int> ss;
	for(int i=aa;i<=bb;i++){
		dist[i]=0;
		ss.push(i);
	}
	while(ss.size()){
		int no=ss.front();
		ss.pop();
		for(auto j:adj[no]){
			if(dist[j]==-1){
				dist[j]=dist[no]+1;
				ss.push(j);
			}
		}
	}
	int mi=-1;
	for(int i=cc;i<=dd;i++){
		if(dist[i]>=0){
			if(mi==-1){
				mi=dist[i];
			}
			mi=min(mi,dist[i]);
		}
	}
	for(int i=0;i<n;i++){
		cout<<dist[i]<<":";
	}
	cout<<endl;*/
	return 0;
}

• 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