Submission #586079

#	Time	Username	Problem	Language	Result	Execution time	Memory
586079		jairRS	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4086 ms	24588 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 1;
vector<int> firstGreaterToTheRight, firstGreaterToTheLeft;
vector<vector<int>> adj;

void init(int N, vector<int> H)
{
	stack<pair<int, int>> s;
	firstGreaterToTheRight = firstGreaterToTheLeft = vector<int>(N, -1);
	adj = vector<vector<int>>(N);
	for (int i = N - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top().first < H[i])
			s.pop();

		if (!s.empty())
			firstGreaterToTheRight[i] = s.top().second;

		s.push({H[i], i});
	}
	while (!s.empty())
		s.pop();
	for (int i = 0; i < N; i++)
	{
		while (!s.empty() && s.top().first < H[i])
			s.pop();

		if (!s.empty())
			firstGreaterToTheLeft[i] = s.top().second;

		s.push({H[i], i});
	}

	for (int i = 0; i < N; i++)
	{
		if (firstGreaterToTheRight[i] != -1)
			adj[i].push_back(firstGreaterToTheRight[i]);
		if (firstGreaterToTheLeft[i] != -1)
			adj[i].push_back(firstGreaterToTheLeft[i]);
	}
}

int minimum_jumps(int A, int B, int C, int D)
{
	int res = INF;

	queue<pair<int, int>> bfs;
	map<int, bool> vis;

	for (int L = A; L <= B; L++)
	{
		bfs.push({L, 0});
		vis[L] = true;
	}

	while (!bfs.empty())
	{
		pair<int, int> cur = bfs.front();
		bfs.pop();
		for (int a : adj[cur.first])
		{
			if (vis[a])
				continue;
			vis[a] = true;
			bfs.push({a, cur.second + 1});
			if (C <= a && a <= D)
				res = min(res, cur.second + 1);
		}
	}

	return (res == INF ? -1 : res);
}

• 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