Submission #1312065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312065		thuhienne	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	414 ms	34900 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];

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] = (h[prev[i]] > h[next[i]] ? prev[i] : next[i]);
		
		jumpright[i][0] = next[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];
		}
	}
	
}

int minimum_jumps(int a,int b,int c,int d) {
	a++,b++,c++,d++;
	if (a != b || c != d) return -1;
	
	int pos = a,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: 0 / 21
• Subtask 7: 0 / 19