제출 #490807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490807		SeDunion	밀림 점프 (APIO21_jumps)	C++17	23 / 100	1358 ms	70028 KiB

jumps

#include "jumps.h"

#include <vector>
#include <iostream>
#include <math.h>
#include <stack>
#include <cassert>

using namespace std;

const int LOG = 20;

int pl[int(3e5)], pr[int(3e5)];

int high[int(3e5)][LOG], low[int(3e5)][LOG];

int H[int(3e5)];

void init(int N, vector<int> a) {
	for (int &i : a) i--;
	for (int i = 0 ; i < N ; ++ i) H[i] = a[i];
	H[N] = N;
	stack<int>st;
	for (int i = 0 ; i < N ; ++ i) {
		while (st.size() && H[st.top()] < H[i]) st.pop();
		pl[H[i]] = st.size() ? H[st.top()] : N;
		st.push(i);
	}
	while (st.size()) st.pop();
	for (int i = N - 1 ; i >= 0 ; -- i) {
		while (st.size() && H[st.top()] < H[i]) st.pop();
		pr[H[i]] = st.size() ? H[st.top()] : N;
		st.push(i);
	}
	pl[N] = pr[N] = N;
	for (int i = 0 ; i <= N ; ++ i) {
		high[i][0] = max(pl[i], pr[i]);
		low[i][0] = pr[i];
		//low[i][0] = min(pl[i], pr[i]);
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i <= N ; ++ i) {
			{
				int where = high[i][j - 1];
				high[i][j] = high[where][j - 1];
			}
			{
				int where = low[i][j - 1];
				low[i][j] = low[where][j - 1];
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	assert(A == B && C == D);
	int s = H[A], t = H[C];
	int ans = 0;
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (high[s][i] <= t) {
			ans += 1 << i;
			s = high[s][i];
		}
	}
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (low[s][i] <= t) {
			ans += 1 << i;
			s = low[s][i];
		}
	}
	if (s != t) return -1;
	return ans;
}

• 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