Submission #554520

#	Time	Username	Problem	Language	Result	Execution time	Memory
554520		hollwo_pelw	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1905 ms	47984 KiB

jumps

#include "jumps.h"

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

const int N = 2e5 + 5;

int big_jmp[18][N], sml_jmp[18][N], rig_jmp[18][N];
int h[N], ljmp[N], rjmp[N];

void init(int n, vector<int> a) {
	a.insert(a.begin(), n + 1); // to 1-based

	static int st[N];

	for (int i = 1, top = 0; i <= n; i++) {
		while (top && a[st[top]] < a[i])
			rjmp[st[top --]] = i;
		st[++ top] = i;
	}

	for (int i = n, top = 0; i >= 1; i--) {
		while (top && a[st[top]] < a[i])
			ljmp[st[top --]] = i;
		st[++ top] = i;
	}

	for (int i = 1; i <= n; i++) {
		rig_jmp[0][i] = rjmp[i];
		big_jmp[0][i] = a[rjmp[i]] > a[ljmp[i]] ? rjmp[i] : ljmp[i];
		sml_jmp[0][i] = a[rjmp[i]] < a[ljmp[i]] ? rjmp[i] : ljmp[i];
	}

	for (int i = 1; i < 18; i++)
		for (int j = 1; j <= n; j++) {
			rig_jmp[i][j] = rig_jmp[i - 1][rig_jmp[i - 1][j]];
			big_jmp[i][j] = big_jmp[i - 1][big_jmp[i - 1][j]];
			sml_jmp[i][j] = sml_jmp[i - 1][sml_jmp[i - 1][j]];
		}

	vector<int> ord(n);
	for (int i = 1; i <= n; i++)
		ord[n - a[i]] = i;

	for (auto u : ord)
		h[u] = h[sml_jmp[0][u]] + 1;
}

inline int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 18; i --; )
		if ((h[v] - h[u]) >> i & 1)
			v = sml_jmp[i][v];
	if (u == v) return u;
	for (int i = 18; i --; )
		if (sml_jmp[i][u] ^ sml_jmp[i][v])
			u = sml_jmp[i][u], v = sml_jmp[i][v];
	return sml_jmp[0][u];
}

int minimum_jumps(int a, int b, int c, int d) {
	++ a, ++ b, ++ c, ++ d; // to 1-based

	int endp = lca(c, d);
	if (h[endp] >= h[b]) return -1;

	if (c == b + 1) return 1;

	int m = lca(b + 1, c - 1);
	if (h[endp] >= h[m]) return -1;

	int l = a, r = b;
	while (l < r) {
		int md = (l + r) >> 1;
		if (h[lca(md, b)] > h[endp])
			r = md;
		else
			l = md + 1;
	}

	int s = lca(l, b), res = 0;

	if (h[s] <= h[m]) return 1;

	for (int i = 18; i --; ) {
		if (big_jmp[i][s] && h[big_jmp[i][s]] > h[m])
			s = big_jmp[i][s], res += 1 << i;
	}

	if (h[big_jmp[0][s]] > h[endp]) return res + 2;

	for (int i = 18; i --; ) {
		if (rig_jmp[i][s] && rig_jmp[i][s] < c)
			s = rig_jmp[i][s], res += 1 << i;
	}

	return res + 1;
}

• 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