Submission #1223527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223527		Jer	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4040 ms	13228 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] = {-1, -1};

	stack<int> s; // H, ind

	for (int i = 0; i < n; i++){
		while (!s.empty() and H[i] > H[s.top()])
			con[s.top()].second = i, s.pop();

		if (!s.empty() and H[s.top()] > H[i])
			con[i].first = s.top();
		
		s.push(i);
	}
}

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: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19