Submission #1177422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177422		stdfloat	밀림 점프 (APIO21_jumps)	C++20	33 / 100	4083 ms	4368 KiB

jumps

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

vector<int> L, R;

void init(int n, vector<int> 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) {
	queue<int> q;
	vector<int> dis((int)L.size(), -1);
	for (int i = A; i <= B; i++) {
		q.push(i);
		dis[i] = 0;
	}

	while (!q.empty()) {
		auto x = q.front(); q.pop();

		if (C <= x && x <= D) return dis[x];

		if (~L[x] && !~dis[L[x]]) {
			q.push(L[x]);
			dis[L[x]] = dis[x] + 1;
		}
		if (~R[x] && !~dis[R[x]]) {
			q.push(R[x]);
			dis[R[x]] = dis[x] + 1;
		}
	}

	return -1;
}

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