답안 #440630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440630	2021-07-02T14:58:41 Z	Elegia	밀림 점프 (APIO21_jumps)	C++17	4 / 100	1116 ms	30880 KB

jumps

#include "jumps.h"

const int MAX_N = 200010, L = 18;

int N;
int h[MAX_N], left[MAX_N][L], right[MAX_N][L];

void init(int _N, std::vector<int> _H) {
	N = _N;
	std::copy(_H.begin(), _H.end(), h + 1);
	static int stack[MAX_N];
	int cnt = 0;
	for (int i = 1; i <= N; ++i) {
		while (cnt && h[i] > h[stack[cnt]])
			right[stack[cnt--]][0] = i;
		left[i][0] = stack[cnt];
		stack[++cnt] = i;
	}
	for (int i = 1; i <= N; ++i) for (int j = 1; j != L; ++j)
		left[i][j] = left[left[i][j - 1]][j - 1];
	std::fill(right[N + 1], right[N + 1] + L, N + 1);
	for (int i = N; i; --i) {
		if (!right[i][0]) right[i][0] = N + 1;
		for (int j = 1; j != L; ++j)
			right[i][j] = right[right[i][j - 1]][j - 1];
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	++A; ++B; ++C; ++D;
	for (int i = L - 1; i >= 0; --i) if (left[D][i] >= C)
		D = left[D][i];
	for (int i = L - 1; i >= 0; --i) if (left[B][i] >= A && h[left[B][i]] < h[D])
		B = left[B][i];
	int ret = 0;
	for (int i = L - 1; i >= 0; --i) if (right[B][i] < C) {
		ret |= 1 << i;
		B = right[B][i];
	}
	if (h[B] > h[D]) return -1;
	return ret + 1;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	169 ms	24584 KB	Output is correct
4	Correct	1116 ms	30800 KB	Output is correct
5	Correct	836 ms	15656 KB	Output is correct
6	Correct	994 ms	30740 KB	Output is correct
7	Correct	759 ms	21132 KB	Output is correct
8	Correct	1071 ms	30752 KB	Output is correct

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	2 ms	200 KB	Output is correct
6	Incorrect	2 ms	328 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	2 ms	200 KB	Output is correct
6	Incorrect	2 ms	328 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	51 ms	24768 KB	Output is correct
6	Correct	64 ms	30732 KB	Output is correct
7	Correct	32 ms	15792 KB	Output is correct
8	Correct	79 ms	30804 KB	Output is correct
9	Correct	13 ms	4844 KB	Output is correct
10	Correct	64 ms	30740 KB	Output is correct
11	Correct	76 ms	30824 KB	Output is correct
12	Correct	61 ms	30880 KB	Output is correct
13	Incorrect	64 ms	30720 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Incorrect	223 ms	14144 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Incorrect	223 ms	14144 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	169 ms	24584 KB	Output is correct
4	Correct	1116 ms	30800 KB	Output is correct
5	Correct	836 ms	15656 KB	Output is correct
6	Correct	994 ms	30740 KB	Output is correct
7	Correct	759 ms	21132 KB	Output is correct
8	Correct	1071 ms	30752 KB	Output is correct
9	Correct	0 ms	200 KB	Output is correct
10	Correct	0 ms	200 KB	Output is correct
11	Correct	0 ms	200 KB	Output is correct
12	Correct	0 ms	200 KB	Output is correct
13	Correct	2 ms	200 KB	Output is correct
14	Incorrect	2 ms	328 KB	Output isn't correct
15	Halted	0 ms	0 KB	-