oj.uz

Submission #463642

# Submission time Handle Problem Language Result Execution time Memory
463642 2021-08-11T12:22:16 Z prvocislo Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 282 ms 38272 KB 
#include "jumps.h"
#include <vector>
using namespace std;

const int logn = 19, maxn = 2e5 + 5;
int jumpl[logn][maxn], jumpr[logn][maxn], high[logn][maxn];
int n, top = 0, h[maxn], stk[maxn];
void init(int N, vector<int> H) 
{
	n = N;
	for (int i = 1; i <= n; i++) h[i] = H[i - 1];
	for (int i = 1; i <= n; i++)
	{
		while (top && h[stk[top - 1]] < h[i]) jumpr[0][stk[top - 1]] = i, top--;
		if (top) jumpl[0][i] = stk[top - 1];
		stk[top++] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		int l = jumpl[0][i], r = jumpr[0][i];
		if (!r || (l && r && h[l] > h[r])) high[0][i] = l;
		else high[0][i] = r;
	}
	for (int l = 1; l < logn; l++) for (int i = 1; i <= n; i++)
	{
		jumpl[l][i] = jumpl[l - 1][jumpl[l - 1][i]];
		jumpr[l][i] = jumpr[l - 1][jumpr[l - 1][i]];
		high[l][i] = high[l - 1][high[l - 1][i]];
	}
}
int minimum_jumps(int a, int b, int c, int d) 
{
	a++, b++, c++, d++;
	for (int l = logn - 1; l >= 0; l--) if (jumpl[l][d] >= c) 
		d = jumpl[l][d];
	for (int l = logn - 1; l >= 0; l--) if (jumpl[l][b] >= a && h[jumpl[l][b]] <= h[d]) 
		b = jumpl[l][b];
	int mx = b; // kym sme nizsie ako mx = maximum ktore budeme musiet prejst, mozeme si chodit ako chceme.
	for (int l = logn - 1; l >= 0; l--) if (jumpr[l][mx] && jumpr[l][mx] < c)
		mx = jumpr[l][mx];
	int i = b, ans = 0;
	for (int l = logn - 1; l >= 0; l--) if (high[l][i] && h[high[l][i]] <= h[mx]) i = high[l][i], ans += (1 << i);
	// i zatial nemoze byt v intervale kde je odpoved, lebo potrebujeme prejst maximum.
	if (high[0][i] && h[high[0][i]] <= h[d]) i = high[0][i], ans++;
	if (c <= i && i <= d) return ans;
	for (int l = logn - 1; l >= 0; l--) if (jumpr[l][i] && jumpr[l][i] < c) i = jumpr[l][i], ans += (1 << i);
	i = jumpr[0][i], ans++;
	if (c <= i && i <= d) return ans;
	return -1;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Incorrect 208 ms 37160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 0 ms 584 KB Output is correct
5 Incorrect 2 ms 584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 0 ms 584 KB Output is correct
5 Incorrect 2 ms 584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 0 ms 584 KB Output is correct
5 Incorrect 46 ms 38272 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 282 ms 21912 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 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 282 ms 21912 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 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Incorrect 208 ms 37160 KB Output isn't correct
4 Halted 0 ms 0 KB -