Submission #1223487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223487		Jer	Rainforest Jumps (APIO21_jumps)	C++20	21 / 100	4086 ms	13256 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int MAXN = 200005;
pair<int, int> con[MAXN];
int n;

void init(int N, std::vector<int> H) {
	n = N;

	for (int i = 0; i < n; i++)
	{
		con[i].first = -1, con[i].second = -1;

		for (int j = i + 1; j < n; j++){
			if (H[i] < H[j])
				{con[i].second = j; break;}
		}

		for (int j = i - 1; j >= 0; j--){
			if (H[i] < H[j])
				{con[i].first = j; break;}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	set<int> vis;
	queue<int> q;

	for (int s = A; s <= B; s++)
		q.push(s);

	int l = 0, curr, len;

	while (!q.empty())
	{
		len = q.size();
		for (int z = len; z > 0; z--){
			curr = q.front(), q.pop();

			if (vis.find(curr) != vis.end())
				continue;

			vis.insert(curr);

			if (curr >= C and curr <= D)
				return l;

			if (con[curr].first != -1)
				q.push(con[curr].first);

			if (con[curr].second != -1)
				q.push(con[curr].second);
		}
		l++;
	}

	return -1;
}

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