Submission #568434

#	Time	Username	Problem	Language	Result	Execution time	Memory
568434		_karan_gandhi	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4077 ms	15904 KiB

jumps

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

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

int n;
vector<int> h;
vector<vector<int>> adj;

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

	// map<int, int> id;
	// vector<int> dup = h;

	// sort(all(dup));
	// int cnt = 0;
	// for (int i = 0; i < n; i++) id[dup[i]] = cnt++;

	// for (int i = 0; i < n; i++) h[i] = id[h[i]];

	stack<int> st;
	for (int i = 0; i < n; i++) {
		// cout << st.size() << endl;
		while (st.size() > 0 && h[st.top()] < h[i]) {
			st.pop();
		}
		if (st.size() != 0) adj[i].push_back(st.top());
		st.push(i);
	}

	while (st.size() != 0) st.pop();
	
	for (int i = n - 1; i >= 0; i--) {
		while (st.size() > 0 && h[st.top()] < h[i]) {
			st.pop();
		}
		if (st.size() != 0) adj[i].push_back(st.top());
		st.push(i);
	}
}

int minimum_jumps(int a, int b, int c, int d) {
	int res = 1e6;

	queue<pair<int, int>> nodes;
	
	for (int start = a; start <= b; start++) {
		nodes.emplace(start, 0);
	}

	vector<bool> vis(n, 0);
	// cout << pl(adj[4]) << endl;

	while (nodes.size() > 0) {
		auto [cur_node, dist] = nodes.front();
		nodes.pop();

		if (vis[cur_node]) continue;
		vis[cur_node] = 1;
		// cout << pl(cur_node) << pl(dist) << endl;

		if (c <= cur_node && cur_node <= d) {
			res = min(res, dist);
			break;
		}

		for (int v : adj[cur_node]) {
			nodes.emplace(v, dist + 1);
		}
	}

	if (res == 1e6) return -1;

	return 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