제출 #1324666

#제출 시각아이디문제언어결과실행 시간메모리
1324666brendonwRainforest Jumps (APIO21_jumps)C++20
4 / 100
2305 ms3488 KiB
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e5;
int h[MAXN], prevmx[MAXN];
int n;
void init(int N, vector<int> H) {
	n = N;
	memset(prevmx, -1, sizeof prevmx);
	copy(H.begin(), H.end(), h);
	set<int> cur;
	int l = 0;
	for (int i = 0; i < n; ++i) {
		prevmx[i] = i - 1;
		while (prevmx[i] != -1 && h[prevmx[i]] <= h[i]) {
			prevmx[i] = prevmx[prevmx[i]];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	for (int i = B; i >= A; --i) {
		for (int j = C; j <= D; ++j) {
			if (prevmx[j] < i) {
				int cnt = 0;
				int curmx = 0;
				for (int k = i; k <= j; ++k) {
					if (curmx < h[k]) {
						curmx = h[k];
						cnt++;
					}
				}
				return cnt - 1;
			}
		}
	}
	return -1;
}
//
//int main() {
//	init(7, {3, 2, 1, 6, 4, 5, 7});
//	cout << minimum_jumps(0, 1, 2, 2);
//	return 0;
//}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...