Submission #1178697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178697		tkm_algorithms	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	100 ms	29712 KiB

jumps

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
//#include "jumps.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 2e5;
const int inf = 1e9;
const int lg = 20;

int uly[N+2][lg], kici[N+2][lg];
vector<int> hh;
int idx[N+2];
int nn;

void init(int n, vector<int> h) {
	nn = n;
	stack<int> st;
	vector<int> a(n, -1), b(n, -1);
	for (int i = n-1; i >= 0; --i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())a[i] = st.top();
		st.push(i);
	}
	
	while (!st.empty())st.pop();
	
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())b[i] = st.top();
		st.push(i);
	}
	
	for (int i = 0; i < n; ++i) {
		hh.push_back(h[i]);
	}
			
	
	for (int i = 0; i < n; ++i) {
		idx[h[i]] = i;
		uly[i][0] = kici[i][0] = h[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < lg; ++j) {
			if (a[i] == -1 && b[i] == -1)continue;
			if (a[i] == -1)uly[i][0] = h[b[i]], kici[i][0] = h[b[i]];
			else if (b[i] == -1)uly[i][0] = h[a[i]], kici[i][0] = h[a[i]];
			else if (h[a[i]] > h[b[i]])uly[i][0] = h[a[i]], kici[i][0] = h[b[i]];
			else uly[i][0] = h[b[i]], kici[i][0] = h[a[i]];
		}
	}
	
	sort(h.rbegin(), h.rend());
	for (int i = 0; i < n; ++i)
		for (int j = 1; j < lg; ++j) {
			uly[idx[h[i]]][j] = uly[idx[uly[idx[h[i]]][j-1]]][j-1];
			kici[idx[h[i]]][j] = kici[idx[kici[idx[h[i]]][j-1]]][j-1];
			//if (i == n-1)cout << uly[0][1] << nl;
		}
	//cout << uly[0][1] << nl;
}

int minimum_jumps(int a, int b, int c, int d) {
	d = idx[hh[a]];
	if (hh[a] > hh[c])return -1;
	int ans = 0;
	for (int i = 19; i >= 0; --i) {
		if ((i > 0 && uly[d][i] == uly[d][i-1]) || uly[d][i] == hh[d])continue;
		if (uly[d][i] <= hh[c]) {
			ans += (1 << i);
			if (uly[d][i] == hh[c])return ans;
			d = idx[uly[d][i]];
		}	
	}
	
	for (int i = 19; i >= 0; --i) {
		if ((i > 0 && kici[d][i] == kici[d][i-1]) || kici[d][i] == hh[d])continue;
		if (kici[d][i] <= hh[c]) {
			ans += (1 << i);
			if (kici[d][i] == hh[c])return ans;
			d = idx[kici[d][i]];
		}	
	}
	
	return -1;
}


// int main() {
// 	int n, q; cin >> n >> q;
// 	vector<int> h(n);
// 	for (int i = 0; i < n; ++i)cin >> h[i];
	
// 	init(n, h);
	
	
	//cout << uly[][]
// 	while (q--) {
// 		int a, b, c, d; cin >> a >> b >> c >> d;
// 		cout << minimum_jumps(a, b, c, d) << nl;
// 	}
// }

• Subtask 1: 0 / 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