Submission #1168342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168342		mertbbm	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	1838 ms	106536 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());

int n;
vector<int>lft[200005];
vector<int>rgt[200005];
bool visited[200005];
int two[21][200005];
int dep[200005];
int two2[21][200005];
int val[21][200005];
int dep2[200005];

void dfs2(int index, int par){
	visited[index]=true;
	for(int x=0;x<20;x++){
		if(two2[x][index]==-1) continue;
		two2[x+1][index]=two2[x][two2[x][index]];
	}
	for(auto it:rgt[index]){
		if(it==par) continue;
		dep2[it]=dep2[index]+1;
		two2[0][it]=index;
		dfs2(it,index);
	}
}

void dfs(int index, int par){
	visited[index]=true;
	for(int x=0;x<20;x++){
		if(two[x][index]==-1) continue;
		two[x+1][index]=two[x][two[x][index]];
		val[x+1][index]=max(val[x][index],val[x][two[x][index]]);
	}
	for(auto it:lft[index]){
		if(it==par) continue;
		dep[it]=dep[index]+1;
		two[0][it]=index;
		val[0][it]=dep2[index]-dep[index];
		dfs(it,index);
	}
}

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 storage[200005];

void init(int n2, vector<int>arr){
	n=n2;
	
	vector<int>d;
	for(int x=0;x<n;x++){
		storage[x]=arr[x];
		while(!d.empty()&&arr[d.back()]<arr[x]){
			d.pop_back();
		}
		if(!d.empty()){
			lft[x].push_back(d.back());
			lft[d.back()].push_back(x);
		}
		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].push_back(d.back());
			rgt[d.back()].push_back(x);
		}
		d.push_back(x);
	}
	
	memset(two,-1,sizeof(two));
	memset(two2,-1,sizeof(two2));
	for(int x=n-1;x>=0;x--){
		if(visited[x]) continue;
		dfs2(x,-1);
	}	
	memset(visited,0,sizeof(visited));
	
	for(int x=0;x<n;x++){
		if(visited[x]) continue;
		dfs(x,-1);
	}
	
	root=new node(0,n+5);
	for(int x=0;x<n;x++){
		root->upd(x,arr[x]);
	}
}

int f(int l2, int a, int b, int c, int d, int mid2){
	int best=d;
	int l=c;
	int r=d;
	int mid;
	
	while(l<=r){
		mid=(l+r)/2;
		if(root->query(c,mid).second.first>mid2){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	int cur=root->query(a,b).second.second;
	int st=cur;
	int offset=dep[cur]-dep2[best];
	int hold=1e9;
	for(int x=19;x>=0;x--){
		if(two[x][cur]==-1) continue;
		if(two[x][cur]<l2) continue;
		if(storage[two[x][cur]]>mid) continue;
		hold=min(hold,val[x][cur]);
		cur=two[x][cur];
	}
	hold+=offset;
	
	if(two[0][cur]!=-1&&two[0][cur]>=l2){
		hold=min(hold,1+dep[st]-dep[two[0][cur]]);
	}
	
	return hold;
}

int minimum_jumps(int a, int b, int c, int d){
	//basic checking
	int midd=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||midd>temp){
		return -1;
	}
	
	//go right 
	int cur=root->query(max(a,best),b).second.second;
	int ans=0;
	for(int x=19;x>=0;x--){
		if(two2[x][cur]==-1) continue;
		if(two2[x][cur]<c){
			cur=two2[x][cur];
			ans+=1<<x;
		}
	}
	ans++;
	//show(ans,ans);
	
	//go left then right
	if(best<a-1){
		ans=min(ans,f(best,a,b,c,d,midd));
	}
	return ans;
}

• 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