Submission #1168418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168418		mertbbm	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	1232 ms	91216 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

inline pi2 combine(const pi2 a, const pi2 b){
	return {min(a.first,b.first),max(a.second,b.second)};
}

struct node{
	int s,e,m;
	node *l,*r;
	pi2 v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v({{0,0},{0,0}}){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void upd(int x, int y){
		if(s==e){
			v={{y,x},{y,x}};
			return;
		}
		if(x<=m) l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	pi2 query(int x, int y){
		if(x>y) return {{0,0},{0,0}};
		if(x<=s&&y>=e){
			return v;
		}
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
}*root;

int n;
vector<int>adj[200005];
int dp[200005];
int dep[200005];
int two[21][200005];
int val[200005];
int two2[21][200005];

void dfs(int index, int par){
	dp[index]=index;
	for(int x=0;x<20;x++){
		if(two[x][index]==-1) continue;
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:adj[index]){
		if(it==par) continue;
		dep[it]=dep[index]+1;
		two[0][it]=index;
		dfs(it,index);
		dp[index]=min(dp[index],dp[it]);
	}
}

void init(int n2, vector<int>arr){
	n=n2;
	int lft[n+5];
	int rgt[n+5];
	memset(lft,-1,sizeof(lft));
	memset(rgt,-1,sizeof(rgt));
	memset(two,-1,sizeof(two));
	memset(two2,-1,sizeof(two2));
	vector<int>d;
	int rt;
	
	for(int x=0;x<n;x++){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()) lft[x]=d.back();
		d.push_back(x);
	}
	
	d.clear();
	for(int x=n-1;x>=0;x--){
		while(!d.empty()&&arr[d.back()]<arr[x]) d.pop_back();
		if(!d.empty()) rgt[x]=d.back();
		d.push_back(x);
		if(lft[x]==-1&&rgt[x]==-1) rt=x;
		else if(lft[x]==-1) adj[rgt[x]].push_back(x);
		else if(rgt[x]==-1) adj[lft[x]].push_back(x);
		else if(arr[lft[x]]>arr[rgt[x]]) adj[lft[x]].push_back(x);
		else adj[rgt[x]].push_back(x);
		
		if(rgt[x]!=-1) two2[0][x]=rgt[x];
		for(int y=0;y<20;y++){
			if(two2[y][x]==-1) continue;
			two2[y+1][x]=two2[y][two2[y][x]];
		}
	}
	dfs(rt,-1);
	root=new node(0,n+5);
	
	for(int x=0;x<n;x++){
		root->upd(x,arr[x]);
		val[x]=arr[x];
	}
}

int minimum_jumps(int a, int b, int c, int d){
	//basic checking
	int target=root->query(b+1,c-1).second.first;
	int temp=root->query(c,d).second.first;
	
	int best=-1;
	int l=0;
	int r=b;
	int mid;
	
	while(l<=r){
		mid=(l+r)/2;
		int hold=root->query(mid,b).second.first;
		if(hold<=temp){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	
	if(best==-1||target>temp){
		return -1;
	}
	
	int ans=0;
	int cur=root->query(max(best,a),b).second.second;
	for(int x=19;x>=0;x--){
		int nxt=two[x][cur];
		if(nxt==-1) continue;
		if(dp[nxt]<best) continue;
		if(val[nxt]>target) continue;
		cur=nxt;
		ans+=1<<x;
	}
	
	//case 1, go rgt
	int add=0;
	int st=cur;
	for(int x=19;x>=0;x--){
		int nxt=two2[x][st];
		if(nxt==-1) continue;
		if(nxt>=c) continue;
		st=nxt;
		add+=1<<x;
	}
	add++;
	
	int add2=1e9;
	if(two[0][cur]!=-1&&two[0][cur]>=best){
		cur=two[0][cur];
		int st=cur;
		add2=0;
		for(int x=19;x>=0;x--){
			int nxt=two2[x][st];
			if(nxt==-1) continue;
			if(nxt>=c) continue;
			st=nxt;
			add2+=1<<x;
		}
		add2+=2;
	}
	
	return ans+min(add,add2);
}

• 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