Submission #1311001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311001		vtnoo	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	439 ms	52944 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<int,int>
using namespace std;
const int MAXN=2e5+5,LOG=20,INF=1e9;
int h[MAXN],sl[MAXN],sr[MAXN],upf[MAXN][LOG],ups[MAXN][LOG],upl[MAXN][LOG],n;
vi adj[MAXN];
void init(int N, std::vector<int> H) {
	n=N;
	stack<ii>mn;
	L(i,0,N-1){
		while(sz(mn)&&mn.top().fst<=H[i]){
			mn.pop();
		}
		sl[i]=sz(mn)?mn.top().snd:i;
		mn.push({H[i],i});
	}
	while(sz(mn))mn.pop(); 
	R(i,N-1,0){
		while(sz(mn)&&mn.top().fst<=H[i]){
			mn.pop();
		}
		sr[i]=sz(mn)?mn.top().snd:i;
		mn.push({H[i],i});
	}
	L(i,0,N-1)h[i]=H[i];
	L(i,0,N-1){
		if(h[sl[i]]>h[sr[i]]){
			upf[i][0]=sl[i];
			ups[i][0]=sr[i];
		}else{
			upf[i][0]=sr[i];
			ups[i][0]=sl[i];
		}
		upl[i][0]=sl[i];
	}
	L(i,1,LOG-1){
		L(j,0,N-1){
			upl[j][i]=upl[upl[j][i-1]][i-1];
			upf[j][i]=upf[upf[j][i-1]][i-1];
			ups[j][i]=ups[ups[j][i-1]][i-1];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	if(A>=C&&A<=D)return 0;
	if(B>=C&&B<=D)return 0;
	int u=B;
	R(i,LOG-1,0){
		if(upl[u][i]==u)continue;
		if(upl[u][i]<A)continue;
		if(h[upl[u][i]]<h[C]){
			u=upl[u][i];
		}
	}
	int ans=0;
	R(i,LOG-1,0){
		if(upf[u][i]==u)continue;
		if(h[upf[u][i]]<h[C]){
			u=upf[u][i];
			ans+=(1<<i);
		}
	}
	if(h[upf[u][0]]==h[C])return ans+1;
	R(i,LOG-1,0){
		if(ups[u][i]==u)continue;
		if(h[ups[u][i]]<h[C]){
			u=ups[u][i];
			ans+=(1<<i);
		}
	}
	if(h[ups[u][0]]==h[C]){
		return ans+1;
	}else return -1;
}

//~ int main(){
	//~ int N,Q;cin>>N>>Q;
	//~ vi H(N);
	//~ L(i,0,N-1)cin>>H[i];
	//~ init(N,H);
	//~ while(Q--){
		//~ int A,B,C,D;cin>>A>>B>>C>>D;
		//~ cout<<minimum_jumps(A,B,C,D)<<endl;
	//~ }
//~ }

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