Submission #1139099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139099		am_aadvik	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	96 ms	50916 KiB

jumps

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

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

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

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][j[x - 1][i]];
		}
}

int minimum_jumps(int a, int b, int c, int d) {
	if (arr[a] > arr[c]) return -1;
	int ans = 0;
	for (int i = 17; i >= 0; --i)
		if (j[i][a] != -1)
			if (arr[j[i][a]] <= arr[c])
				ans += (1 << i), a = j[i][a];
	if (a == c) return ans;

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

• 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