Submission #786712

#	Time	Username	Problem	Language	Result	Execution time	Memory
786712		ToniB	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1025 ms	63952 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
#define X first
#define Y second
using namespace std;
const int MAXN = 2e5 + 2;
const int LOG = 18;
const int OFF = 1 << LOG + 1;

int n, nxt[MAXN][LOG], prv[MAXN][LOG], nxt_max[MAXN][LOG], prv_max[MAXN][LOG];
pair<int, int> tour[OFF];
vector<int> h;

pair<int, int> f(int x, int l, int r, int ql, int qr){
	if(ql > r || l > qr) return {-1, -1};
	if(ql <= l && r <= qr) return tour[x];
	int mid = (l + r) >> 1;
	pair<int, int> L = f(x * 2 + 1, l, mid, ql, qr);
	pair<int, int> R = f(x * 2 + 2, mid + 1, r, ql, qr);
	return max(L, R);
}
void con(int x, int l, int r){
	if(l == r){
		tour[x] = {h[l], l};
		return ;
	}
	int mid = (l + r) >> 1;
	con(x * 2 + 1, l, mid);
	con(x * 2 + 2, mid + 1, r);
	tour[x] = max(tour[x * 2 + 1], tour[x * 2 + 2]);
}

void init(int _n, vector<int> _h){
	n = _n; h = _h;
	con(0, 0, n - 1);
	stack<int> s;
	for(int i = 0; i < n; ++i){
		while(!s.empty() && h[s.top()] < h[i]) s.pop();
		if(s.empty()) prv[i][0] = -1;
		else prv[i][0] = s.top();
		s.push(i);
		
		nxt_max[i][0] = prv_max[i][0] = h[i];
	}

	while(!s.empty()) s.pop();
	for(int i = n - 1; i >= 0; --i){
		while(!s.empty() && h[s.top()] < h[i]) s.pop();
		if(s.empty()) nxt[i][0] = n;
		else nxt[i][0] = s.top();
		s.push(i);
	}
	
	for(int j = 1; j < LOG; ++j){
		for(int i = 0; i < n; ++i){
			if(prv[i][j - 1] == -1) prv[i][j] = -1;
			else prv[i][j] = prv[prv[i][j - 1]][j - 1];
			if(nxt[i][j - 1] == n) nxt[i][j] = n;
			else nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
			
			prv_max[i][j] = max(prv_max[i][j - 1], prv_max[max(0, i - (1 << j - 1))][j - 1]);
			nxt_max[i][j] = max(nxt_max[i][j - 1], nxt_max[min(n - 1, i + (1 << j - 1))][j - 1]);
		}
	}
}

int minimum_jumps(int a, int b, int c, int d){
	if(max(a, c) <= min(b, d)) return 0;
	int ret = 0;
	if(b < c){
		pair<int, int> maks = f(0, 0, n - 1, b + 1, d);
		if(maks.Y < c) return -1;
		int idx = b;
		for(int i = LOG - 1; i >= 0; --i){
			if(idx - (1 << i) >= -1 && prv_max[idx][i] < maks.X){
				idx -= 1 << i;
			}
		}
		idx = max(a, idx + 1);
		if(idx > b) return -1;
		int node = f(0, 0, n - 1, idx, b).Y;
		assert(a <= node && node <= b);
		for(int i = LOG - 1; i >= 0; --i){
			if(nxt[node][i] < c){
				node = nxt[node][i];
				ret += 1 << i;
			}
		}
		assert(nxt[node][0] <= d && nxt[node][0] >= c);
	} else {
		pair<int, int> maks = f(0, 0, n - 1, c, b - 1);
		if(maks.Y > d) return -1;
		int idx = a;
		for(int i = LOG - 1; i >= 0; --i){
			if(idx + (1 << i) <= n && nxt_max[idx][i] < maks.X){
				idx += 1 << i;
			}
		}
		idx = min(b, idx - 1);
		if(idx < a) return -1;
		int node = f(0, 0, n - 1, a, idx).Y;
		assert(a <= node && node <= b);
		for(int i = LOG - 1; i >= 0; --i){
			if(prv[node][i] > d){
				node = prv[node][i];
				ret += 1 << i;
			}
		}
		assert(prv[node][0] <= d && prv[node][0] >= c);
	}
	return ret + 1;
}

Compilation message (stderr)

jumps.cpp:8:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    8 | const int OFF = 1 << LOG + 1;
      |                      ~~~~^~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:61:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |    prv_max[i][j] = max(prv_max[i][j - 1], prv_max[max(0, i - (1 << j - 1))][j - 1]);
      |                                                                    ~~^~~
jumps.cpp:62:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |    nxt_max[i][j] = max(nxt_max[i][j - 1], nxt_max[min(n - 1, i + (1 << j - 1))][j - 1]);
      |                                                                        ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19