Submission #1178420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178420		tkm_algorithms	Rainforest Jumps (APIO21_jumps)	C++20	37 / 100	4090 ms	15140 KiB

jumps

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
//#include "jumps.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 2e5;
const int inf = 1e9;

vector<int> g[N+1];
int nn, vis[N+1];
bool ok = true;

void init(int n, vector<int> h) {
	nn = n;
	stack<int> st;
	vector<int> a(n, -1), b(n, -1);
	for (int i = n-1; i >= 0; --i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())a[i] = st.top();
		st.push(i);
	}
	
	while (!st.empty())st.pop();
	
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())b[i] = st.top();
		st.push(i);
	}
	
	for (int i = 0; i < n; ++i) {
		if (i > 0 && h[i] <= h[i-1])ok = false;
		if (a[i] != -1)g[i].push_back(a[i]);
		if (b[i] != -1)g[i].push_back(b[i]);
	}
	
}

int minimum_jumps(int a, int b, int c, int d) {
	if (ok)return c-b;
	memset(vis, 0, sizeof vis);
	queue<pair<int, int>> q;
	for (int i = a; i <= b; ++i) {
		q.push({0, i});
		vis[i] = 1;
	}
	
	int ans = inf;
	while (!q.empty()) {
		int u = q.front().second, w = q.front().first;
		q.pop();
		if (w >= ans)continue;
		if (u >= c && u <= d)return w;
		for (auto i: g[u]) {
			if (!vis[i])
				q.push({w+1, i}), vis[i] = 1;
		}
	}
	
	if (ans == inf)ans = -1;
	return ans;
}

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