Submission #552772

#	Time	Username	Problem	Language	Result	Execution time	Memory
552772		QwertyPi	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1212 ms	53784 KiB

jumps

#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++){
		if(h[pl[i]] == inf || h[pr[i]] == inf) p[i] = h[pl[i]] != inf ? pl[i] : pr[i];
		else p[i] = 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, C - 1) > 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(C <= pr[ST] && pr[ST] <= D) return ans + 1;
      	if(C <= pr[pl[ST]] && pr[pl[ST]] <= D) return ans + 2;
      	if(h[pl[ST]] < mx_CD && h[pr[ST]] < h[pl[ST]]) ST = pl[ST], ans++;
	}
	{
		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 (stderr)

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 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19