Submission #1081051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081051		pawned	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4075 ms	35648 KiB

jumps

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "jumps.h"

const int MAX = 2e5 + 5;

int N;
vi H;

vi nl(MAX, -1);
vi nr(MAX, -1);

vi adj[MAX];

void init(int N_g, vi H_g) {
	N = N_g; H = H_g;
	vi all[N + 1];	// all pos of height i
	for (int i = 0; i < N; i++) {
		all[H[i]].pb(i);
	}
	set<int> cs;	// current set of all greater
	for (int i = N; i >= 1; i--) {
		for (int x : all[i]) {
			auto it = cs.lower_bound(x);
			if (it != cs.begin()) {
				auto it2 = it;
				it2--;
				nl[x] = *(it2);
			}
			if (it != cs.end())
				nr[x] = *it;
		}
		for (int x : all[i])
			cs.insert(x);
	}
/*	cout<<"nl: ";
	for (int i = 0; i < N; i++) {
		cout<<nl[i]<<" ";
	}
	cout<<endl;
	cout<<"nr: ";
	for (int i = 0; i < N; i++) {
		cout<<nr[i]<<" ";
	}
	cout<<endl;*/
	for (int i = 0; i < N; i++) {
		if (nl[i] != -1)
			adj[i].pb(nl[i]);
		if (nr[i] != -1)
			adj[i].pb(nr[i]);
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	vi dist(N, 1e9);
	queue<int> q;
	for (int i = A; i <= B; i++) {
		dist[i] = 0;
		q.push(i);
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adj[x]) {
			if (dist[y] == 1e9) {
				dist[y] = dist[x] + 1;
				q.push(y);
			}
		}
	}
	int ans = 1e9;
	for (int i = C; i <= D; i++) {
		ans = min(ans, dist[i]);
	}
	if (ans != 1e9)
		return ans;
	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