Submission #977947

#	Time	Username	Problem	Language	Result	Execution time	Memory
977947		rshohruh	Rainforest Jumps (APIO21_jumps)	C++17	77 / 100	4041 ms	57024 KiB

jumps

#include "jumps.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
int n, l;
vector<int> h;
vector<pair<int, int>> a;
vector<vector<int>> up, A;

using node = int;
struct segment_tree{
	vector<node> t;
	vector<int> a;
	int n;

	node merge(node l, node r){
		return a[l] > a[r] ? l : r;
	}

	void build(int v, int l, int r){
		if(l == r){
			t[v] = l-1;
			return;
		}
		int m = (l + r) >> 1;
		build(v<<1, l, m);
		build(v<<1|1, m+1, r);
		t[v] = merge(t[v<<1], t[v<<1|1]);
	}
	
	node getmax(int v, int l, int r, int L, int R, int x){
		if(a[t[v]] < x) return -1;
		if(l == r) return t[v];
		int m = (l + r) / 2;
		if(R <= m) return getmax(v*2, l, m, L, R, x);
		else if(L > m) return getmax(v*2+1, m+1, r, L, R, x);
		else{
			int ans = getmax(v*2+1, m+1, r, m+1, R, x);
			if(ans != -1) return ans;
			else return getmax(v*2, l, m, L, m, x);
		}
	}

	node getmax(int L, int R, int x){
		return getmax(1, 1, n, L+1, R+1, x);
	}

	node get(int v, int l, int r, int L, int R){
		if(L == l && R == r)
			return t[v];
		
		int m = (l + r) >> 1;
		if(R <= m) return get(v<<1, l, m, L, R);
		else if(L > m) return get(v<<1|1, m+1, r, L, R);
		else {
			return merge(
				get(v<<1, l, m, L, m),
				get(v<<1|1, m+1, r, m+1, R)
			);
		}
	}
	node get(int L, int R){
		return get(1,1,n,L+1, R+1);
	}
	segment_tree(vector<int>a):a(a){
		n = (int)a.size();
		t.resize(n<<2);
		build(1, 1, n);
	}
	segment_tree() {}
};

segment_tree st;

void init(int N, std::vector<int> H)
{
	cin.tie(nullptr)->sync_with_stdio(false);
	n = N+1;
	h = H;
	l = ceil(log2(n));

	h.push_back(n);
	a.resize(n);
	up.resize(n, vector<int>(l+1));
	A.resize(n, vector<int>(l+1));
	st = segment_tree(h);
	stack<int> st;
	for(int i = 0; i < n; ++i){
		while(!st.empty() && h[st.top()] < h[i]){
			a[st.top()].second = i;
			st.pop();
		}
		st.push(i);
	}
	while(!st.empty()){
		a[st.top()].second = st.top();
		st.pop();
	}

	for(int i = n-1; i >= 0; --i){
		while(!st.empty() && h[st.top()] < h[i]){
			a[st.top()].first = i;
			st.pop();
		}
		st.push(i);
	}
	while(!st.empty()){
		a[st.top()].first = st.top();
		st.pop();
	}

	vector<int> inv_h(n+1);
	for(int i = 0; i < n; ++i) inv_h[h[i]] = i;
	for(int i = n; i > 0; --i){
		int id = inv_h[i];

		if(h[a[id].first] > h[a[id].second]) up[id][0] = a[id].first;
		else up[id][0] = a[id].second;
		
		A[id][0] = a[id].second;

		// cerr << id << ' ' << up[id][0] << ' ';
		for(int j = 1; j <= l; ++j){
			up[id][j] = up[up[id][j-1]][j-1];
			A[id][j] = A[A[id][j-1]][j-1];
			// cerr << up[id][j] << ' ';
		}
		// cerr << endl;
		// cout << a[id].first << ' ' << id << ' ' << a[id].second << endl;
	}

}

int ans(int L, int R){
	int ans = 0;
	for(int i = l; i >= 0; --i){
		if(h[up[L][i]] <= h[R]){
			L = up[L][i];
			ans += (1<<i);
		}
	}
	for(int i = l; i >= 0; --i){
		if(h[A[L][i]] <= h[R]){
			L = A[L][i];
			ans += (1<<i);
		}
	}
	if(L == R) return ans;
	return inf;
}

int minimum_jumps(int A, int B, int C, int D)
{
	// return 0;
	int res = inf;
	for(int id = C; id <= D; ++id){
		if(h[B] > h[id]) continue;

		int L = st.getmax(A, B, h[id]);
		// cerr << "\n----" << L << "---\n";
		int mx_id = st.get(max(L+1, A), B);

		// int mx = 0, mx_id = B;
		// for(int i = B; i >= A; --i){
		// 	if(h[i] > h[id]) break;
		// 	if(h[i] > mx){
		// 		mx = h[i];
		// 		mx_id = i;
		// 	}
		// }
		res = min(res, ans(mx_id, id));
	}
	return (res == inf ? -1 : res);
}

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