oj.uz

Submission #552759

# Submission time Handle Problem Language Result Execution time Memory
552759 2022-04-23T20:18:22 Z QwertyPi Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1174 ms 53656 KB 
#include "jumps.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 200002;
const int inf = 1 << 20;
int mx[N][20], h[N], pl[N], pr[N], p[N];
int bl[N][20], bl_r[N][20];
int n;

void mx_prec(){
	for(int i = 1; i <= n; i++){
		mx[i][0] = h[i];
	}
	for(int j = 1; j < 20; j++){
		for(int i = 1; i <= n + 1 - (1 << j); i++){
			mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
		}
	}
}

void bl_prec(){
	bl[0][0] = 0, bl[n + 1][0] = n + 1;
	for(int i = 1; i <= n; i++){
		bl[i][0] = p[i];
	}
	for(int j = 1; j < 20; j++){
		for(int i = 0; i <= n + 1; i++){
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}
	bl_r[0][0] = 0, bl_r[n + 1][0] = n + 1;
	for(int i = 1; i <= n; i++){
		bl_r[i][0] = pr[i];
	}
	for(int j = 1; j < 20; j++){
		for(int i = 0; i <= n + 1; i++){
			bl_r[i][j] = bl_r[bl_r[i][j - 1]][j - 1];
		}
	}
}

int mx_qry(int l, int r){
	if(l <= 0 || r >= n + 1 || l > r + 1) return inf;
	if(l == r + 1) return 0;
	int d = __lg(r - l + 1);
	return max(mx[l][d], mx[r - (1 << d) + 1][d]);
}

void init(int N, std::vector<int> H) {
	::n = N;
	for(int i = 1; i <= N; i++){
		h[i] = H[i - 1];
	}
	h[0] = h[n + 1] = inf;
	pl[0] = 0, pr[0] = 0, pl[n + 1] = n + 1, pr[n + 1] = n + 1;
	vector<pii> L {{inf, 0}};
	for(int i = 1; i <= n; i++){
		while(L.back().fi < h[i]) L.pop_back();
		pl[i] = L.back().se;
		L.push_back({h[i], i});
	}
	vector<pii> R {{inf, n + 1}};
	for(int i = n; i >= 1; i--){
		while(R.back().fi < h[i]) R.pop_back();
		pr[i] = R.back().se;
		R.push_back({h[i], i});
	}
	p[0] = 0, p[n + 1] = n + 1;
	for(int i = 1; i <= n; i++){
		p[i] = h[pl[i]] == inf || h[pl[i]] < h[pr[i]] ? pr[i] : pl[i];
	}
	mx_prec();
	bl_prec();
}

int minimum_jumps(int A, int B, int C, int D) {
	A++; B++; C++; D++;
	if(mx_qry(B + 1, C - 1) > mx_qry(C, D)) return -1;
	if(h[B] > mx_qry(C, D)) return -1;
	int mx_CD = mx_qry(C, D);
	int mx_gap = mx_qry(B + 1, C - 1);
	int mx_val_AB = inf, mx_idx_AB = -1;
	{
		int l = 1, r = B - A + 1;
		while(l != r){
			int m = (l + r + 1) / 2;
			if(mx_qry(B - m + 1, B) < mx_qry(C, D)){
				l = m;
			}else{
				r = m - 1;
			}
		}
		mx_val_AB = mx_qry(B - l + 1, B);
	}
	if(mx_val_AB == 0) return -1;
	{
		int l = 0, r = B - A + 1;
		while(l != r){
			int m = (l + r + 1) / 2;
			if(mx_qry(B - m + 1, B) < mx_val_AB){
				l = m;
			}else{
				r = m - 1;
			}
		}
		mx_idx_AB = B - l;
	}
	assert(h[mx_idx_AB] == mx_val_AB);
	int ST = mx_idx_AB;
	int ans = 0;
	{
		int steps = 0;
		for(int j = 19; j >= 0; j--){
			if(h[bl[ST][j]] < mx_gap) steps += (1 << j), ST = bl[ST][j];
		}
		ans += steps;
	}
	{
		if(h[pl[ST]] < mx_CD && !(C <= pr[ST] && pr[ST] <= D)) ans++, ST = pl[ST];
	}
	{
		int steps = 0;
		for(int j = 19; j >= 0; j--){
			if(bl_r[ST][j] < C) steps += (1 << j), ST = bl_r[ST][j];
		}
		ans += steps;
	}
	{
		if(ST < C) ST = pr[ST], ans++;
		if(C <= ST && ST <= D) return ans;
		else return -1;
	}
}

Compilation message

jumps.cpp: In function 'void mx_prec()':
jumps.cpp:19:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   19 |    mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
      |                                              ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 218 ms 42756 KB Output is correct
4 Correct 1141 ms 53560 KB Output is correct
5 Correct 901 ms 27192 KB Output is correct
6 Correct 1174 ms 53616 KB Output is correct
7 Correct 897 ms 36748 KB Output is correct
8 Correct 1152 ms 53560 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 102 ms 41892 KB Output is correct
6 Correct 129 ms 51892 KB Output is correct
7 Correct 49 ms 26700 KB Output is correct
8 Correct 120 ms 52016 KB Output is correct
9 Correct 9 ms 8016 KB Output is correct
10 Correct 118 ms 51928 KB Output is correct
11 Correct 123 ms 53656 KB Output is correct
12 Correct 117 ms 53144 KB Output is correct
13 Correct 139 ms 53164 KB Output is correct
14 Incorrect 119 ms 51924 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 218 ms 23844 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 218 ms 23844 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 218 ms 42756 KB Output is correct
4 Correct 1141 ms 53560 KB Output is correct
5 Correct 901 ms 27192 KB Output is correct
6 Correct 1174 ms 53616 KB Output is correct
7 Correct 897 ms 36748 KB Output is correct
8 Correct 1152 ms 53560 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Incorrect 2 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -