Submission #526324

#	Time	Username	Problem	Language	Result	Execution time	Memory
526324		Vladithur	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	3170 ms	40980 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200001, logn = 20;
int t[maxn * 4], t2[maxn * 4], up[maxn][logn], up2[maxn][logn];
vector<int> h;

void update(int v, int tl, int tr, int i, int x) {
	if (tl == tr - 1) {
		t[v] = x;
		t2[v] = tl;
	} else {
		int tm = (tl + tr) / 2;
		if (i < tm) update(2*v + 1, tl, tm, i, x);
		else update(2*v + 2, tm, tr, i, x);
		t[v] = max(t[2*v + 1], t[2*v + 2]);
		if (t[2*v + 1] > t[2*v + 2]) t2[v] = t2[2*v + 1];
		else t2[v] = t2[2*v + 2];
	}
}

pair<int, int> query(int v, int tl, int tr, int l, int r) {
	if (l >= r) return {0, 0};
	else if (tl == l && tr == r) return {t[v], t2[v]};
	else {
		int tm = (tl + tr) / 2;
		auto r1 = query(2*v + 1, tl, tm, l, min(r, tm));
		return max(r1, query(2*v + 2, tm, tr, max(l, tm), r));
	}
}
	
	
int n;

void init(int N, std::vector<int> H) {
	n = N;
	h = H;
	n++;
	h.push_back(n + 1);
	for (int i = 0; i < n; i++) update(0, 0, n, i, h[i]);
	vector<pair<int, int>> b;
	for (int i = 0; i < n; i++) b.emplace_back(h[i], i);
	sort(b.rbegin(), b.rend());
	for (auto tp: b) {
		int i = tp.second;
		int g1 = i, g2 = i;
		
		{
			int lb = 0, ub = i - 1;
			while (lb <= ub) {
				int tm = (lb + ub) / 2;
				auto r = query(0, 0, n, tm, i + 1);
				if (r.second != i) {
					g1 = r.second;
					lb = tm + 1;
				} else {
					ub = tm - 1;
				}
			}
		}
		
		{
			int lb = i + 1, ub = n - 1;
			while (lb <= ub) {
				int tm = (lb + ub) / 2;
				auto r = query(0, 0, n, i, tm + 1);
				if (r.second != i) {
					g2 = r.second;
					ub = tm - 1;
				} else {
					lb = tm + 1;
				}
			}
		}
		
		if (h[g2] > h[g1]) swap(g2, g1);
		
		if (g1 == i) g1 = n - 1;
		if (g2 == i) g2 = n - 1;
		
		up[i][0] = g1;
		up2[i][0] = g2;
		for (int j = 1; j < logn; j++) {
			up[i][j] = up[up[i][j - 1]][j - 1];
			up2[i][j] = up2[up2[i][j - 1]][j - 1];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	
	int x = query(0, 0, n, C, D + 1).first;
	int y = query(0, 0, n, B + 1, C).first;
	if (y >= x) return -1;
	
	int lb = A, ub = B, tans = -1;
	while (lb <= ub) {
		int tm = (lb + ub) / 2;
		if (query(0, 0, n, tm, B + 1).first < x) {
			tans = tm;
			ub = tm - 1;
		} else {
			lb = tm + 1;
		}
	}
	
	if (tans == -1) return -1;
	int v = query(0, 0, n, tans, B + 1).second;
	
	int ans = 0;
	
	for (int i = logn - 1; i >= 0; i--) {
		if (h[up[v][i]] <= y) {
			v = up[v][i];
			ans += (1 << i);
		}
	}
	if (h[v] < y && h[up[v][0]] < x) {
		ans++;
		v = up[v][0];
	}
	
	//cout << v << ' ' << ans << endl;
	
	if (h[up[v][0]] < x) {
		return ans + 1;
	}
	
	for (int i = logn - 1; i >= 0; i--) {
		if (h[up2[v][i]] <= y) {
			v = up2[v][i];
			ans += (1 << i);
		}
	}
	
	if (h[v] < y && h[up2[v][0]] <= y) {
		ans++;
		v = up2[v][0];
	}
	
	return ans + 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