제출 #1177451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177451		stdfloat	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	4025 ms	52136 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
// #include "stub.cpp"
using namespace std;

vector<int> H, L, R;

vector<vector<int>> sp1, sp2;

void init(int n, vector<int> h) {
	H = h;
	
	stack<int> s;
	L = R = vector<int>(n);
	for (int i = 0; i < n; i++) {
		while (!s.empty() && h[s.top()] < h[i]) s.pop();

		L[i] = (s.empty() ? -1 : s.top());

		s.push(i);
	}

	while (!s.empty()) s.pop();

	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && h[i] > h[s.top()]) s.pop();

		R[i] = (s.empty() ? -1 : s.top());

		s.push(i);
	}

	sp1 = sp2 = vector<vector<int>>(n, vector<int>(20, -1));
	for (int i = 0; i < n; i++) {
		sp1[i][0] = R[i];
		sp2[i][0] = (~L[i] && (!~R[i] || H[L[i]] > H[R[i]]) ? L[i] : R[i]);
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			if (~sp1[j][i - 1]) sp1[j][i] = sp1[sp1[j][i - 1]][i - 1];
			if (~sp2[j][i - 1]) sp2[j][i] = sp2[sp2[j][i - 1]][i - 1];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	assert(C == D);

	int x = -1;
	for (int i = B; i >= A && H[i] <= H[C]; i--)
		if (!~x || H[i] > H[x]) x = i;

	if (!~x) return -1;

	int cnt = 0;
	for (int i = 19; i >= 0; i--) {
		if (~sp2[x][i] && H[sp2[x][i]] <= H[C]) {
			x = sp2[x][i];
			cnt += 1 << i;
		}
	}
	for (int i = 19; i >= 0; i--) {
		if (~sp1[x][i] && H[sp1[x][i]] <= H[C]) {
			x = sp1[x][i];
			cnt += (1 << i);
		}
	}

	return (x == C ? cnt : -1);
}

• 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