Submission #1139259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139259		am_aadvik	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	553 ms	46888 KiB

jumps

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include<set>
#include<algorithm>
using namespace std;

vector<int> arr;
int n, l[18][200005], r[18][200005], j[18][200005], idx[200005];

int mx(int a, int s) {
	if ((a == -1) || (s == -1)) return max(a, s);
	return ((arr[a] > arr[s]) ? a : s);
}

void init(int tn, vector<int> a) {
	n = tn, arr = a;
	for (int i = 0; i < n; ++i)
		idx[arr[i]] = i;
	memset(l, -1, sizeof(l));
	memset(r, -1, sizeof(r));
	memset(j, -1, sizeof(j));

	vector<int> q;
	for (int i = 0; i < n; ++i) {
		while (q.size() && (q.back() < arr[i])) q.pop_back();
		if (q.size()) l[0][i] = idx[q.back()];
		q.push_back(arr[i]);
	}
	q.clear();
	for (int i = n - 1; i >= 0; --i) {
		while (q.size() && (q.back() < arr[i])) q.pop_back();
		if (q.size()) r[0][i] = idx[q.back()];
		q.push_back(arr[i]);
	}

	for (int i = 0; i < n; ++i)
		j[0][i] = mx(l[0][i], r[0][i]);
	for (int x = 1; x < 18; ++x)
		for (int i = 0; i < n; ++i) {
			l[x][i] = ((l[x - 1][i] == -1) ? -1 : l[x - 1][l[x - 1][i]]);
			r[x][i] = ((r[x - 1][i] == -1) ? -1 : r[x - 1][r[x - 1][i]]);
			j[x][i] = ((j[x - 1][i] == -1) ? -1 : j[x - 1][j[x - 1][i]]);
		}
}

int solve(int s, int e) {
	if (arr[s] > arr[e]) return -1;
	int ans = 0;
	for (int i = 17; i >= 0; --i)
		if (j[i][s] != -1)
			if (arr[j[i][s]] <= arr[e])
				ans += (1 << i), s = j[i][s];
	if (s == e) return ans;

	if (arr[r[0][s]] <= arr[e]) {
		for (int i = 17; i >= 0; --i)
			if (r[i][s] != -1)
				if (arr[r[i][s]] <= arr[e])
					ans += (1 << i), s = r[i][s];
	}
	else
		for (int i = 17; i >= 0; --i)
			if (l[i][s] != -1)
				if (arr[l[i][s]] <= arr[e])
					ans += (1 << i), s = l[i][s];
	if (s == e) return ans;
	return -1;
}

int minimum_jumps(int a, int b, int c, int d) {
	for (int i = 17; i >= 0; --i)
		if ((l[i][b] >= a) && (arr[l[i][b]] < arr[c]))
			b = l[i][b];
	return solve(b, c);
}

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