Submission #501384

#	Time	Username	Problem	Language	Result	Execution time	Memory
501384		Adominator	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1369 ms	74048 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()

#define rep(i, a, b) for(ll i=a; i<b; i++) 
#define repd(i, a, b) for(ll i=a; i>=b; i--) 

int n, h[int(2e5+10)];
int jmp_l[int(2e5+10)][30];
int jmp_r[int(2e5+10)][30];
int jmp_mx[int(2e5+10)][30];

void init(int N, std::vo<int> H) {
	n=N+2;

	h[0]=1e8;
	rep(i, 0, N) 
		h[i+1]=H[i];
	h[n-1]=1e8;

	stack<int> st;
	rep(i, 0, n) {
		jmp_r[i][0]=i;
		while(sz(st) && h[st.top()]<h[i]) 
			jmp_r[st.top()][0]=i, st.pop();
		st.push(i);
	}

	while(sz(st)) 
		st.pop();

	repd(i, n-1, 0) {
		jmp_l[i][0]=i;
		while(sz(st) && h[st.top()]<h[i]) 
			jmp_l[st.top()][0]=i, st.pop();
		st.push(i);
	}

	rep(i, 0, n) {
		jmp_mx[i][0]=jmp_r[i][0];
		if(h[jmp_l[i][0]]>h[jmp_r[i][0]]) 
			jmp_mx[i][0]=jmp_l[i][0];
	}

	rep(i, 1, 30) 
		rep(k, 0, n) {
			jmp_l[k][i]=jmp_l[jmp_l[k][i-1]][i-1];
			jmp_r[k][i]=jmp_r[jmp_r[k][i-1]][i-1];
			jmp_mx[k][i]=jmp_mx[jmp_mx[k][i-1]][i-1];
		}
}

int minimum_jumps(int A, int B, int C, int D) {	
	A++, B++, C++, D++;
	if(B+1==C) {
		if(jmp_r[B][0]>D) 
			return -1;
		else 
			return 1;
	}

	int ind=B+1;
	repd(i, 29, 0) 
		if(jmp_r[ind][i]<C) 
			ind=jmp_r[ind][i];

	if(h[B]>h[ind]) {
		if(jmp_r[B][0]>D) 
			return -1;
		else 
			return 1;
	}

	int cur=B;
	repd(i, 29, 0) 
		if(h[jmp_l[cur][i]]<h[ind] && jmp_l[cur][i]>=A) 
			cur=jmp_l[cur][i];

	int ans=0;
	if(jmp_l[cur][0]>=A) {
		if(jmp_r[jmp_l[cur][0]][0]<=D)
			return 1;
	}
	else {
		repd(i, 29, 0) 
			if(h[jmp_mx[cur][i]]<=h[ind]) {	
				cur=jmp_mx[cur][i];
				ans+=1<<i;
			}

		if(cur==ind) {
			if(jmp_r[cur][0]>D) 
				return -1;
			else 
				return ans+1;
		}

		if(jmp_l[cur][0] && jmp_r[jmp_l[cur][0]][0]<=D) 
			return ans+2;
	}

	repd(i, 29, 0) 
		if(jmp_r[cur][i]<C) {
			cur=jmp_r[cur][i];
			ans+=1<<i;
		}

	if(jmp_r[cur][0]>=C && jmp_r[cur][0]<=D)
		return ans+1;
	else 
		return -1;
}

• 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