Submission #1139106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139106		am_aadvik	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	456 ms	51588 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][i] == -1) ? -1 : j[x - 1][j[x - 1][i]]);
		}
}

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

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

/*int main()
{
	init(15, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
	for(int i = 0; i < 15; ++i)
		for (int j = i + 1; j < 15; ++j) {
			int res = minimum_jumps(i, i, j, j);
			if (res != (j - i)) {
				cout << "Fail: " << i << " " << j;
				return 0;
			}
		}
	cout << "Success!";
}*/

• Subtask 1: 4 / 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