제출 #934625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934625		MinaRagy06	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4051 ms	5068 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];
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);
	}
}
int minimum_jumps(int l, int r, int s, int e) {
	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) {
		while (prv[cur] != -1 && nxt[prv[cur]] <= e && nxt[prv[cur]] != nxt[cur]) {
			cur = prv[cur];
			ans++;
		}
		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