Submission #786727

#	Time	Username	Problem	Language	Result	Execution time	Memory
786727		ToniB	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1194 ms	35756 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_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 = 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);

		prv_max[i][0] = h[i];
	}

	for(int i = 0; i < n; ++i){
		for(int j = i + 1; j < n; ++j){
			if(h[j] > h[i]){
				assert(nxt[i][0] == j);
				nxt[i][0] = j; break;
			}
			if(j == n - 1){
				assert(nxt[i][0] == n);
				nxt[i][0] = n;
			}
		}
	}

	for(int j = 1; j < LOG; ++j){
		for(int i = 0; i < n; ++i){
			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]);
		}
	}
}

int minimum_jumps(int a, int b, int c, int d){
	int ret = 0;
	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) >= a - 1 && prv_max[idx][i] < maks.X){
			idx -= 1 << i;
		}
	}
	++idx;
	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);
	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:65:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   65 |    prv_max[i][j] = max(prv_max[i][j - 1], prv_max[max(0, 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