Submission #934695

#	Time	Username	Problem	Language	Result	Execution time	Memory
934695		MinaRagy06	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	745 ms	46028 KiB

jumps

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "jumps.h"
using namespace std;
#define ll long long
 
const int N = 200'005;
int nxt[N][18], prv[N][18], lift[N][18], n;
vector<int> a;
bool ST1 = 1;
void init(int _n, vector<int> _a) {
	a = _a;
	n = _n;
	for (int i = 0; i < n; i++) {
		ST1 &= a[i] == i + 1;
	}
	stack<int> s;
	s.push(n);
	for (int i = n - 1; i >= 0; i--) {
		while (s.top() != n && a[s.top()] < a[i]) {
			s.pop();
		}
		nxt[i][0] = s.top();
		s.push(i);
	}
	while (s.size()) s.pop();
	s.push(-1);
	for (int i = 0; i < n; i++) {
		while (s.top() != -1 && a[s.top()] < a[i]) {
			s.pop();
		}
		prv[i][0] = s.top();
		s.push(i);
	}
	for (int i = 0; i < n; i++) {
		if (prv[i][0] == -1 || a[nxt[i][0]] > a[prv[i][0]]) {
			lift[i][0] = nxt[i][0];
		} else {
			lift[i][0] = prv[i][0];
		}
	}
	lift[n][0] = n;
	nxt[n][0] = n;
	prv[n][0] = -1;
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i <= n; i++) {
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
			nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
			prv[i][j] = prv[i][j - 1];
			if (prv[i][j] != -1) prv[i][j] = prv[prv[i][j]][j - 1];
		}
	}
}
int minimum_jumps(int l, int r, int s, int e) {
#ifndef MINA
	if (ST1) {
		return s - r;
	}
#endif
	if (nxt[r][0] > e) {
		return -1;
	}
	int lst = r;
	for (int j = 17; j >= 0; j--) {
		if (l <= prv[lst][j] && nxt[prv[lst][j]][0] <= e) {
			lst = prv[lst][j];
		}
	}
	if (lst == -1) return -1;
	int cur = lst, ans = 0;
	for (int j = 17; j >= 0; j--) {
		int New = lift[cur][j];
		if (New != n && nxt[New][0] < s) {
			cur = New;
			ans += 1 << j;
		}
	}
	if (nxt[lift[cur][0]][0] <= e && nxt[cur][0] < s) {
		cur = lift[cur][0];
		ans++;
	}
	for (int j = 17; j >= 0; j--) {
		if (nxt[cur][j] < s) {
			cur = nxt[cur][j];
			ans += 1 << j;
		}
	}
	cur = nxt[cur][0];
	ans++;
	if (cur > e) {
		return -1;
	}
	return ans;
}

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