Submission #1177460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177460		stdfloat	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	558 ms	76404 KiB

jumps

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

vector<int> lg, H, L, R;

vector<vector<int>> sp, sp1, sp2;

void init(int n, vector<int> h) {
	H = h;
	
	stack<int> s;
	L = R = vector<int>(n);
	for (int i = 0; i < n; i++) {
		while (!s.empty() && h[s.top()] < h[i]) s.pop();

		L[i] = (s.empty() ? -1 : s.top());

		s.push(i);
	}

	while (!s.empty()) s.pop();

	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && h[i] > h[s.top()]) s.pop();

		R[i] = (s.empty() ? -1 : s.top());

		s.push(i);
	}

	lg.assign(n + 1, 0);
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i >> 1] + 1;

	sp = sp1 = sp2 = vector<vector<int>>(n, vector<int>(20, -1));
	for (int i = 0; i < n; i++) {
		sp[i][0] = i;
		sp1[i][0] = R[i];
		sp2[i][0] = (~L[i] && (!~R[i] || H[L[i]] > H[R[i]]) ? L[i] : R[i]);
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			if (j + (1 << i) <= n) {
				int x = sp[j][i - 1], y = sp[j + (1 << (i - 1))][i - 1];
				sp[j][i] = (H[x] > H[y] ? x : y);
			}
			if (~sp1[j][i - 1]) sp1[j][i] = sp1[sp1[j][i - 1]][i - 1];
			if (~sp2[j][i - 1]) sp2[j][i] = sp2[sp2[j][i - 1]][i - 1];
		}
	}
}

int fnd(int l, int r) {
	int x = lg[r - l + 1], y = sp[l][x], z = sp[r - (1 << x) + 1][x];
	return (H[y] > H[z] ? y : z);
}

int minimum_jumps(int A, int B, int C, int D) {
	if (H[B] > H[C]) return -1;

	int l = A, r = B;
	while (l <= r) {
		int md = (l + r) >> 1;

		if (H[fnd(md, B)] > H[C]) l = md + 1;
		else r = md - 1;
	}

	int x = fnd(l, B), cnt = 0;
	for (int i = 19; i >= 0; i--) {
		if (~sp2[x][i] && H[sp2[x][i]] <= H[C]) {
			x = sp2[x][i];
			cnt += 1 << i;
		}
	}
	for (int i = 19; i >= 0; i--) {
		if (~sp1[x][i] && H[sp1[x][i]] <= H[C]) {
			x = sp1[x][i];
			cnt += (1 << i);
		}
	}

	return (x == C ? cnt : -1);
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 0 / 19