제출 #464017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464017		prvocislo	밀림 점프 (APIO21_jumps)	C++17	100 / 100	1764 ms	47936 KiB

jumps

#include "jumps.h"
#include <vector>
using namespace std;

const int logn = 19, maxn = 2e5+5;
//const int logn = 19, maxn = 10;
int jumpl[logn][maxn], jumpr[logn][maxn], high[logn][maxn];
int n, top, h[maxn], stk[maxn];
void init(int N, vector<int> H) 
{
	n = N, top = 0;
	for (int i = 1; i <= n; i++) h[i] = H[i - 1];
	for (int i = 1; i <= n; i++)
	{
		while (top && h[stk[top - 1]] < h[i]) jumpr[0][stk[top - 1]] = i, top--;
		if (top) jumpl[0][i] = stk[top - 1];
		stk[top++] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		int l = jumpl[0][i], r = jumpr[0][i];
		if (!r || (l && r && h[l] > h[r])) high[0][i] = l;
		else high[0][i] = r;
	}
	for (int l = 1; l < logn; l++) for (int i = 1; i <= n; i++)
	{
		jumpl[l][i] = jumpl[l - 1][jumpl[l - 1][i]];
		jumpr[l][i] = jumpr[l - 1][jumpr[l - 1][i]];
		high[l][i] = high[l - 1][high[l - 1][i]];
	}
}
int minimum_jumps(int a, int b, int c, int d) 
{
	a++, b++, c++, d++;
	for (int l = logn - 1; l >= 0; l--)
		if (jumpl[l][d] >= c) 
			d = jumpl[l][d];
	for (int l = logn - 1; l >= 0; l--) 
		if (jumpl[l][b] >= a && h[jumpl[l][b]] <= h[d]) 
			b = jumpl[l][b];
	int mx = b; // kym sme nizsie ako mx = maximum ktore budeme musiet prejst, mozeme si chodit ako chceme.
	for (int l = logn - 1; l >= 0; l--)
		if (jumpr[l][mx] && jumpr[l][mx] < c)
			mx = jumpr[l][mx];
	int i = b, ans = 0;
	for (int l = logn - 1; l >= 0; l--) 
		if (high[l][i] && h[high[l][i]] <= h[mx]) 
			i = high[l][i], ans += (1 << l);
	// i zatial nemoze byt v intervale kde je odpoved, lebo potrebujeme prejst maximum.
	if (jumpr[0][i] >= c && jumpr[0][i] <= d) return ans + 1;
	if (high[0][i] && h[high[0][i]] <= h[d]) 
		i = high[0][i], ans++;
	for (int l = logn - 1; l >= 0; l--) 
		if (jumpr[l][i] && jumpr[l][i] < c) 
			i = jumpr[l][i], ans += (1 << l);
	i = jumpr[0][i], ans++;
	if (c <= i && i <= d) return ans;
	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