Submission #934689

#	Time	Username	Problem	Language	Result	Execution time	Memory
934689		MinaRagy06	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4054 ms	19276 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], prv[N], 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] = 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 || a[nxt[i]] > a[prv[i]]) {
			lift[i][0] = nxt[i];
		} else {
			lift[i][0] = prv[i];
		}
	}
	lift[n][0] = n;
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i <= n; i++) {
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
		}
	}
}
int minimum_jumps(int l, int r, int s, int e) {
#ifndef MINA
	if (ST1) {
		return s - r;
	}
#endif
	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;
	for (int j = 17; j >= 0; j--) {
		int New = lift[cur][j];
		if (New != n && nxt[New] < s) {
			cur = New;
			ans += 1 << j;
		}
	}
	if (nxt[lift[cur][0]] <= e && nxt[cur] < s) {
		cur = lift[cur][0];
		ans++;
	}
	while (cur < s) {
		cur = nxt[cur];
		ans++;
	}
// 	bool ok = 0;
// 	while (cur < s) {
// 		if (ok || nxt[cur] >= s || prv[cur] == -1 || a[nxt[cur]] > a[prv[cur]] || nxt[prv[cur]] > e) {
// 			if (prv[cur] == -1 || nxt[prv[cur]] > e) {
// 				ok = 1;
// 			}
// 			cur = nxt[cur];
// 		} else {
// 			cur = prv[cur];
// 		}
// 		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: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19