제출 #1177447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177447		stdfloat	밀림 점프 (APIO21_jumps)	C++20	0 / 100	4083 ms	5028 KiB

jumps

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

vector<int> H, L, R;

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);
	}
}

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;

	int cnt = 0;
	while (x != C) {
		bool tr = false;
		if (~L[x] && (!~R[x] || H[R[x]] > H[C] || H[L[x]] > H[R[x]]) && H[L[x]] <= H[C]) {
			x = L[x];
			tr = true;
		}
		else if (~R[x] && (!~L[x] || H[L[x]] > H[C] || H[L[x]] < H[R[x]]) && H[R[x]] <= H[C]) {
			x = R[x];
			tr = true;
		}

		if (!tr) break;

		cnt++;
	}

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19