Submission #559015

#	Time	Username	Problem	Language	Result	Execution time	Memory
559015		LastRonin	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1092 ms	47944 KiB

jumps

#include "jumps.h"
 
#include <bits/stdc++.h>
 
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
 
using namespace std;
 
const int N = 2e5 + 10;
 
int bp[N][18];
int bp2[N][18];
int bp3[N][18];
int z[N], h[N];
int Le[N], Ri[N];
 
void init(int n, vector<int> H) {
	for(int j = 1; j <= n; j++)
		h[j] = H[j - 1];
    stack<int> L, R;
	for(int j = 1; j <= n; j++)
		z[h[j]] = j;
	for(int i = 1; i <= n; i++) {
		while(L.size() && L.top() <= h[i])L.pop();	
		if(L.size())
			Le[i] = L.top();
		L.push(h[i]);		
	}	
	for(int i = n; i >= 1; i--) {
		while(R.size() && R.top() <= h[i])R.pop();	
		if(R.size())
			Ri[i] = R.top();
		R.push(h[i]);		
	}
	for(int j = n; j >= 1; j--) {
		bp[z[j]][0] = (Le[z[j]] > Ri[z[j]] ? Le[z[j]] : Ri[z[j]]);
		bp2[z[j]][0] = Ri[z[j]];
		bp3[z[j]][0] = Le[z[j]];
		for(int i = 1; i < 18; i++) {
			bp[z[j]][i] = bp[z[bp[z[j]][i - 1]]][i - 1];
			bp2[z[j]][i] = bp2[z[bp2[z[j]][i - 1]]][i - 1];
			bp3[z[j]][i] = bp3[z[bp3[z[j]][i - 1]]][i - 1];
		}
	}	
}
 
int minimum_jumps(int A, int B, int C, int D) {	
	A++, B++, C++, D++;
	ll X = B;
	for(int j = 17; j >= 0; j--) {
		if(bp2[X][j] == 0)continue;
		if(z[bp2[X][j]] < C) {
			X = z[bp2[X][j]];
		}
	}
	X = z[bp2[X][0]];	
	if(X > D || X == 0)return -1;
	C = X;
 
	for(int j = 17; j >= 0; j--) {
		if(bp3[B][j] == 0)continue;
		if(bp3[B][j] <= h[C] && z[bp3[B][j]] >= A) {
			B = z[bp3[B][j]];
		}		
	}
	ll F = z[Le[B]];
	if(F >= A && z[Ri[F]] <= D && z[Ri[F]] >= C)return 1;
	ll cnt = 0;
	for(int j = 17; j >= 0; j--) {
		if(bp[B][j] == 0)continue;
		if(bp[B][j] <= h[C]) {
			cnt += (1<<j);
			B = z[bp[B][j]];
		}
	}
	F = z[Le[B]];
	ll mnans = N + 1;
	if(F != 0 && z[Ri[F]] <= D && z[Ri[F]] >= C)mnans = cnt + 2;
	for(int j = 17; j >= 0; j--) {
		if(bp2[B][j] == 0)continue;
		if(bp2[B][j] <= h[C]) {
			cnt += (1<<j);
			B = z[bp2[B][j]];
		}
	}
	return min(mnans, cnt);
}

• 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