Submission #725993

#	Time	Username	Problem	Language	Result	Execution time	Memory
725993		SanguineChameleon	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1683 ms	116260 KiB

jumps

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

const int maxN = 2e5 + 20;
const int maxL = 20;
int lg[maxN];
pair<int, int> range[maxN];
pair<int, int> sparse[maxN][maxL];
pair<int, int> par[maxN][maxL];
int pos[maxN];
int ch[maxN][2];
int H[maxN];
int N;
int node_cnt;
int time_in[maxN];
int time_out[maxN];
int id[maxN];
pair<int, int> jump[maxN][maxL];
int T;

int get(int lt, int rt) {
	int k = lg[rt - lt + 1];
	return max(sparse[lt][k], sparse[rt - (1 << k) + 1][k]).second;
}

int dfs1(int lt, int rt) {
	if (lt > rt) {
		return -1;
	}
	int u = node_cnt++;
	range[u] = {lt, rt};
	int mt = get(lt, rt);
	id[mt] = u;
	pos[u] = mt;
	ch[u][0] = dfs1(lt, mt - 1);
	ch[u][1] = dfs1(mt + 1, rt);
	if (ch[u][0] != -1) {
		par[ch[u][0]][0] = {u, pos[ch[u][0]]};
	}
	if (ch[u][1] != -1) {
		par[ch[u][1]][0] = {u, pos[ch[u][1]]};
	}
	return u;
}

void dfs4(int u, int cur_0, int cur_1) {
	time_in[u] = ++T;
	if (ch[u][0] != -1) {
		jump[ch[u][0]][0] = {cur_1, max(pos[ch[u][0]], pos[u])};
		dfs4(ch[u][0], u, cur_1);
	}
	if (ch[u][1] != -1) {
		jump[ch[u][1]][0] = {cur_0, max(pos[ch[u][1]], pos[u])};
		dfs4(ch[u][1], cur_0, u);
	}
	time_out[u] = ++T;
}

bool anc(int u, int v) {
	return (u != -1 && v != -1) && (time_in[u] <= time_in[v] && time_out[v] <= time_out[u]);
}

void init(int _N, vector<int> _H) {
	for (int i = 2; i < maxN; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	N = _N;
	for (int i = 0; i < N; i++) {
		H[i] = _H[i];
		sparse[i][0] = {H[i], i};
	}
	for (int k = 1; k < maxL; k++) {
		for (int i = 0; i + (1 << k) <= N; i++) {
			sparse[i][k] = max(sparse[i][k - 1], sparse[i + (1 << (k - 1))][k - 1]);
		}
	}
	dfs1(0, N - 1);
	dfs4(0, -1, -1);
	par[0][0] = {-1, -1};
	jump[0][0] = {-1, -1};
	for (int k = 1; k < maxL; k++) {
		for (int u = 0; u < N; u++) {
			int v = jump[u][k - 1].first;
			if (v == -1) {
				jump[u][k] = {-1, -1};
			}
			else {
				jump[u][k] = {jump[v][k - 1].first, max(jump[u][k - 1].second, jump[v][k - 1].second)};
			}
			v = par[u][k - 1].first;
			if (v == -1) {
				par[u][k] = {-1, -1};
			}
			else {
				par[u][k] = {par[v][k - 1].first, max(par[u][k - 1].second, par[v][k - 1].second)};
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	int lt = A;
	int rt = B;
	int start = -1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (H[get(mt, B)] < H[get(C, D)]) {
			start = id[get(mt, B)];
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	int fin = id[get(C, D)];
	if (!anc(fin, start)) {
		return -1;
	}
	int cur = start;
	int res = 0;
	for (int k = maxL - 1; k >= 0; k--) {
		int nxt = jump[cur][k].first;
		int mx = jump[cur][k].second;
		if (C > mx && anc(fin, nxt)) {
			cur = nxt;
			res += (1 << k);
		}
	}
	for (int k = maxL - 1; k >= 0; k--) {
		int nxt = par[cur][k].first;
		int mx = par[cur][k].second;
		if (nxt != -1 && C > mx) {
			cur = nxt;
			res += (1 << k);
		}
	}
	return res;
}

• 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