Submission #725804

#	Time	Username	Problem	Language	Result	Execution time	Memory
725804		SanguineChameleon	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4094 ms	8112 KiB

jumps

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

const int maxN = 2e5 + 20;
pair<int, int> range[maxN];
pair<int, int> par[maxN];
int pos[maxN];
int ch[maxN][2];
int H[maxN];
int N;
int node_cnt;
int A, B, C, D;
int start_u;

int dfs1(int lt, int rt) {
	if (lt > rt) {
		return -1;
	}
	int u = node_cnt++;
	range[u] = {lt, rt};
	pair<int, int> mx = {H[lt], lt};
	for (int i = lt; i <= rt; i++) {
		mx = max(mx, make_pair(H[i], i));
	}
	int mt = mx.second;
	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]] = {u, 0};
	}
	if (ch[u][1] != -1) {
		par[ch[u][1]] = {u, 1};
	}
	return u;
}

void init(int _N, vector<int> _H) {
	N = _N;
	for (int i = 0; i < N; i++) {
		H[i] = _H[i];
	}
	dfs1(0, N - 1);
}

void dfs3(int u) {
	if (u == -1) {
		return;
	}
	int mt = pos[u];
	if (B < mt) {
		dfs3(ch[u][0]);
	}
	else if (A > mt) {
		dfs3(ch[u][1]);
	}
	else {
		start_u = u;
		return;
	}
}

void dfs2(int u) {
	if (u == -1) {
		return;
	}
	int mt = pos[u];
	if (D < mt) {
		dfs2(ch[u][0]);
	}
	else if (C > mt) {
		dfs2(ch[u][1]);
	}
	else {
		dfs3(u);
	}
}

int minimum_jumps(int _A, int _B, int _C, int _D) {
	A = _A;
	B = _B;
	C = _C;
	D = _D;
	start_u = -1;
	dfs2(0);
	if (start_u == -1) {
		return -1;
	}
	int prv = -1;
	int streak = 0;
	int cnt = 0;
	int cur = start_u;
	while (true) {
		if (C <= pos[cur] && pos[cur] <= D) {
			assert(cnt > 0);
			return (cnt - 1) / 2 + streak;
		}
		if (par[cur].second != prv) {
			streak = 1;
			cnt++;
		}
		else {
			streak++;
		}
		prv = par[cur].second;
		cur = par[cur].first;
	}
	return 0;
}

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