oj.uz

Submission #440647

# Submission time Handle Problem Language Result Execution time Memory
440647 2021-07-02T15:38:41 Z Elegia Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1156 ms 45768 KB 
#include "jumps.h"

const int MAX_N = 200010, L = 18;

int N;
int h[MAX_N], left[MAX_N][L], right[MAX_N][L], gr[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], ord[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];
	}
	for (int i = 1; i <= N; ++i) ord[h[i]] = i;
	std::fill(gr[N + 1], gr[N + 1] + L, N + 1);
	for (int i = N; i; --i) {
		int j = ord[i];
		gr[j][0] = (h[left[j][0]] > h[right[j][0]] ? left : right)[j][0];
		for (int k = 1; k != L; ++k) gr[j][k] = gr[gr[j][k - 1]][k - 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 = 1, thres = 0;
	if (B + 1 < C) {
		int X = B + 1, Y = C - 1;
		for (int i = L - 1; i >= 0; --i) if (left[Y][i] >= X)
			Y = left[Y][i];
		thres = h[Y];
	}
	for (int i = L - 1; i >= 0; --i) if (gr[B][i] < C && h[gr[B][i]] <= thres) {
		ret += 1 << i;
		B = gr[B][i];
	}
	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;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 185 ms 36372 KB Output is correct
4 Correct 1088 ms 45712 KB Output is correct
5 Correct 706 ms 23104 KB Output is correct
6 Correct 1156 ms 45572 KB Output is correct
7 Correct 664 ms 31296 KB Output is correct
8 Correct 797 ms 45724 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory 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 3 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory 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 3 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 113 ms 36828 KB Output is correct
6 Correct 130 ms 45680 KB Output is correct
7 Correct 68 ms 23468 KB Output is correct
8 Correct 132 ms 45768 KB Output is correct
9 Correct 18 ms 7112 KB Output is correct
10 Correct 132 ms 45632 KB Output is correct
11 Correct 97 ms 45636 KB Output is correct
12 Correct 85 ms 45668 KB Output is correct
13 Incorrect 84 ms 45632 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory 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 289 ms 21028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory 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 289 ms 21028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 185 ms 36372 KB Output is correct
4 Correct 1088 ms 45712 KB Output is correct
5 Correct 706 ms 23104 KB Output is correct
6 Correct 1156 ms 45572 KB Output is correct
7 Correct 664 ms 31296 KB Output is correct
8 Correct 797 ms 45724 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 3 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -