Submission #1128305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128305		ByeWorld	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	1006 ms	104068 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int LOG = 20;
const int MAXA = 1e6;
const int INF = 2e9;

int n, h[MAXN];
int le[MAXN], ri[MAXN], anc[MAXN][LOG+5];
int up[MAXN][LOG+5], dw[MAXN][LOG+5];
pii mx[MAXN][LOG+5];

pii MX(int le, int ri){
	if(le > ri) return pii(-INF, 0);
	int len = log2(ri-le+1);
	return max(mx[le][len], mx[ri-(1<<len)+1][len]);
}
void init(int N, std::vector<int> H) {
	n = N;
	for(int i=1; i<=n; i++){
		h[i] = H[i-1];
		mx[i][0] = {h[i], i};
	}
	for(int j=1; j<LOG; j++){
		for(int i=1; i+(1<<j)-1<=n; i++){
			mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
		}
	}

	h[0] = h[n+1] = -INF;
	ri[n+1] = n+1;
	for(int j=0; j<LOG; j++)
		for(int i=0; i<=n+1; i++)
			anc[i][j] = up[i][j] = n+1,
			dw[i][j] = 0; 

	vector <pii> vec; 
	for(int i=n; i>=1; i--){
		while(!vec.empty() && h[i] > vec.back().fi) vec.pop_back();
		if(!vec.empty()){
			ri[i] = vec.back().se; 
			// cout << i << ' ' << vec.back().se << " pp\n";
		} else ri[i] = n+1;
		up[i][0] = ri[i];
		vec.pb({h[i], i});
	}
	vec.clear(); 
	for(int i=1; i<=n; i++){
		while(!vec.empty() && h[i] > vec.back().fi) vec.pop_back();
		if(!vec.empty()){
			le[i] = vec.back().se;
			// cout << i << ' ' << vec.back().se << " pp\n";
		} else le[i] = 0;
		dw[i][0] = le[i];
		vec.pb({h[i], i});
	}
		
	
	for(int i=1; i<=n; i++){
		if(h[le[i]] > h[ri[i]]) anc[i][0] = le[i];
		else anc[i][0] = ri[i];
	}
	for(int j=1; j<LOG; j++)
		for(int i=1; i<=n; i++)
			anc[i][j] = anc[ anc[i][j-1] ][j-1],
			up[i][j] = up[ up[i][j-1] ][j-1],
			dw[i][j] = dw[ dw[i][j-1] ][j-1];
}

int cost(int sta, int en){
	int tot = 0;
	for(int i=LOG-1; i>=0; i--){
		if(anc[sta][i]!=n+1 && anc[sta][i]!=0 && h[ anc[sta][i] ] <= h[en]){
			sta = anc[sta][i];
			tot += (1<<i);
		}
	}
	for(int i=LOG-1; i>=0; i--){
		if(up[sta][i]!=n+1 && up[sta][i] <= en){
			sta = up[sta][i];
			tot += (1<<i);
		}
	}
	if(sta == en) return tot;
	return INF;
}
int minimum_jumps(int A, int B, int C, int D) {
	// goto right
	A++; B++; C++; D++;
	if(B == C-1){
		if(C<=ri[B] && ri[B]<=D) return 1;
		return -1;
	}

	int mx = MX(B+1, C-1).fi;
	int jump = 0, idxj = 0;
	if(MX(A, B).fi > mx){ // bisa langsung
		int l=A, r=B, mid=0, cnt=A;
		while(l<=r){ // cari yg paling kanan lebih dr mx
			mid = md;
			if(MX(mid, B).fi > mx) l = mid+1, cnt = mid;
			else r = mid-1;
		}
		jump = 0; idxj = cnt;
	} else { // harus ke kiri dulu
		int nw = MX(A, B).se; // dari range max

		int l=1, r=A-1, mid=0, cnt=0;
		while(l<=r){ // paling kanan yg more
			mid = md;
			if(MX(mid, B).fi > mx) l = mid+1, cnt = mid;
			else r = mid-1;
		}
		// harus ke cnt
		for(int i=LOG-1; i>=0; i--){ // ke kiri
			if(anc[nw][i]!=n+1 && anc[nw][i]!=0 && 
				h[ anc[nw][i] ] <= h[cnt]){ // ke cnt
				nw = anc[nw][i]; jump += (1<<i);
			}
		}
		idxj = cnt;
	}
	// cout << idxj << " idx\n";
	// 	cout << jump << " jump\n";
	int ans = INF;
	if(idxj!=0 && idxj!=n+1
		&& C<=ri[idxj] && ri[idxj]<=D) ans = jump+1;

	int l=A, r=B, mid=0, cnt=B;
	while(l<=r){ // cari max range yg < mx
		mid = md;
		if(MX(mid, B).fi < mx) cnt = mid, r = mid-1;
		else l = mid+1;
	}
	int sta = MX(cnt, B).se;
	// cout << sta << " sta\n";

	l=C, r=D, mid=0, cnt=C;
	while(l<=r){
		mid = md;
		if(MX(C, mid).fi > mx) cnt = mid, r = mid-1;
		else l = mid+1;
	}
	if(MX(C, D).fi < mx) return -1; // gk bisa ke sana

	int en = cnt;

	ans = min(ans, cost(sta, en));

	return (ans > n ? -1 : ans);
}

• 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