Submission #491554

#	Time	Username	Problem	Language	Result	Execution time	Memory
491554		SeDunion	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1258 ms	85428 KiB

jumps

#include "jumps.h"

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

#define cerr if(false)cerr

using namespace std;

const int LOG = 20;

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

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

int canR[int(3e5)][LOG], lowR[int(3e5)][LOG];

int H[int(3e5)], id[int(3e5)];

int spmx[int(3e5)][LOG];

int lg[int(3e5)];

int getmax(int l, int r) {
	int j = lg[r - l + 1];
	return max(spmx[l][j], spmx[r - (1 << j) + 1][j]);
}

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;
	for (int i = 0 ; i <= N ; ++ i) id[H[i]] = i;
	//id[N] = 0;
	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];
		lowR[i][0] = id[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];
				//canR[i][j] = max(canR[i][j - 1], canR[where][j - 1]);
			}
			{
				int where = low[i][j - 1];
				low[i][j] = low[where][j - 1];
				lowR[i][j] = id[low[i][j]];
			}
		}
	}
	for (int i = 0 ; i <= N ; ++ i) {
		//canR[i][0] = max({id[i], id[pr[i]], id[pl[i]]});
		canR[i][0] = max(id[i], id[pr[i]]);
		int cur = i;
		for (int j = 1 ; j < LOG ; ++ j) {
			cur = high[cur][j - 1];
			//canR[i][j] = max({id[cur], id[pr[cur]], id[pl[cur]]});
			canR[i][j] = max(id[cur], id[pr[cur]]);
		}
	}
	for (int j = 0 ; j < 2 ; ++ j) {
		for (int i = 0 ; i <= N ; ++ i) {
			cerr << canR[H[i]][j] << " \n"[i == N];
		}
	}
	cerr << "\n\n";
	for (int i = 0 ; i <= N ; ++ i) {
		spmx[i][0] = H[i];
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i + (1 << j) - 1 <= N ; ++ i) {
			spmx[i][j] = max(spmx[i][j - 1], spmx[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 2 ; i < int(3e5) ; ++ i) lg[i] = lg[i >> 1] + 1;
}

int minimum_jumps(int A, int B, int C, int D) {
	int dmx = getmax(C, D);
	int s = -1;
	{
		int l = A, r = B;
		while (l <= r) {
			int m = (l + r) >> 1;
			if (getmax(m, B) <= dmx) s = getmax(m, B), r = m - 1;
			else l = m + 1;
		}
	}
	if (s == -1) return -1;
	int ans = 0;
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (high[s][i] <= dmx && canR[s][i] < C) {
			ans += 1 << i;
			s = high[s][i];
		}
	}
	cerr << s << " s\n";
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (low[s][i] <= dmx && lowR[s][i] < C) {
			ans += 1 << i;
			s = low[s][i];
		}
	}
	cerr << s << " s\n";
	s = low[s][0], ans++;
	cerr << s << " s\n";
	cerr << "\n";
	if (id[s] < C || id[s] > D) return -1;
	return ans;
}

• 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