Submission #934669

#	Time	Username	Problem	Language	Result	Execution time	Memory
934669		MinaRagy06	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4089 ms	20944 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], nxt2[N][18], prv[N], prv2[N][18];
vector<int> a;
void init(int n, vector<int> _a) {
	a = _a;
	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] = 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] = s.top();
		s.push(i);
	}
	for (int i = 0; i < n; i++) {
		if (prv[i] != -1 && nxt[prv[i]] != nxt[i]) {
			prv2[i][0] = prv[i];
		} else {
			prv2[i][0] = -1;
		}
	}
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i < n; i++) {
			prv2[i][j] = prv2[i][j - 1];
			if (prv2[i][j] != -1) prv2[i][j] = prv2[prv2[i][j]][j - 1];
		}
	}
// 	for (int i = 0; i < n; i++) {
// 		if (prv2[i][0] != -1
// 	}
}
int minimum_jumps(int l, int r, int s, int e) {
	if (nxt[r] > e) {
		return -1;
	}
	int mx = -1, lst = -1;
	for (int i = r; i >= l; i--) {
		if (a[i] > mx) {
			mx = a[i];
			if (nxt[i] <= e) {
				lst = i;
			} else {
				break;
			}
		}
	}
	if (lst == -1) return -1;
	int cur = lst, ans = 0;
	while (cur < s) {
		for (int j = 17; j >= 0; j--) {
			if (prv2[cur][j] != -1 && nxt[prv2[cur][j]] <= e && nxt[prv2[cur][j]] < s) {
				cur = prv2[cur][j];
				ans += 1 << j;
			}
		}
		if (nxt[cur] < s && prv2[cur][0] != -1 && nxt[prv2[cur][0]] <= e) cur = prv2[cur][0], ans++;
		cur = nxt[cur];
		ans++;
		if (prv2[cur][0] == -1) {
			break;
		}
	}
	while (cur < s) {
		cur = nxt[cur];
		ans++;
	}
	if (cur > e) {
		return -1;
	}
	return ans;
}

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