Submission #1312077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312077		thuhienne	Rainforest Jumps (APIO21_jumps)	C++20	44 / 100	473 ms	49764 KiB

jumps

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

using ll = long long;

#define re exit(0);
#define prev __prev__
#define next __next__

const int maxn = 200009;
const int inf = 1e9;
const int LOG = 18;

int n,h[maxn];
int prev[maxn],next[maxn];

int jumpopt[maxn][LOG + 1],jumpright[maxn][LOG + 1],sparse[maxn][LOG + 1];

int better(int a,int b) {
	return h[a] < h[b] ? b : a;
}

int getmax(int l,int r) {
	int i = __lg(r - l + 1);
	return better(sparse[l][i],sparse[r - (1 << i) + 1][i]);
}

void init(int _n,vector <int> _h) {
	n = _n;
	for (int i = 0;i < n;i++) h[i + 1] = _h[i];
	h[0] = h[n + 1] = inf;
	
	stack <int> st;
	st.push(0);
	for (int i = 1;i <= n;i++) {
		while (h[st.top()] <= h[i]) st.pop();
		prev[i] = st.top();
		st.push(i);
	}
	
	while (st.size()) st.pop();
	st.push(n + 1);
	for (int i = n;i >= 1;i--) {
		while (h[st.top()] <= h[i]) st.pop();
		next[i] = st.top();
		st.push(i);
	}
	
	for (int i = 1;i <= n;i++) {
		if (prev[i] == 0) jumpopt[i][0] = next[i];
		else if (next[i] == n + 1) jumpopt[i][0] = prev[i];
		else jumpopt[i][0] = better(next[i],prev[i]);
		
		jumpright[i][0] = next[i];
		
		sparse[i][0] = i;
	}
	
	for (int j = 1;j <= LOG;j++) {
		for (int i = 1;i <= n;i++) {
			jumpopt[i][j] = jumpopt[jumpopt[i][j - 1]][j - 1];
			jumpright[i][j] = jumpright[jumpright[i][j - 1]][j - 1];
			
			if (i + (1 << j) - 1 <= n) sparse[i][j] = better(sparse[i][j - 1],sparse[i + (1 << (j - 1))][j - 1]);
		}
	}
	
}

int minimum_jumps(int a,int b,int c,int d) {
	a++,b++,c++,d++;
	if (c != d) return -1;
	
	int dicken = prev[c];
	if (dicken >= b) return -1;
	a = max(a,dicken + 1);
	
	int pos = getmax(a,b),aim = c,res = 0;
	
	for (int j = LOG;j >= 0;j--) {
		int temp = jumpopt[pos][j];
		if (h[temp] < h[aim]) pos = temp,res += 1 << j;
	}
	
	for (int j = LOG;j >= 0;j--) {
		int temp = jumpright[pos][j];
		if (h[temp] < h[aim]) pos = temp,res += 1 << j;
	}
	
	pos = jumpright[pos][0];
	res++;
	
	if (pos != aim) return -1;
	return res;
	 
}

• Subtask 1: 0 / 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