Submission #860226

#	Time	Username	Problem	Language	Result	Execution time	Memory
860226		mychecksedad	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	793 ms	46916 KiB

jumps

#include<jumps.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;


int n, L[N], R[N], up[N][K][2];
vector<int> H;
void init(int _n, vector<int> h){
	n = _n;
	H = h;
	
	H.pb(MOD);

	deque<int> q;
	L[0] = n;
	q.pb(0);
	for(int i = 1; i < n; ++i){
		while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
		if(!q.empty()) L[i] = q.back();
		else L[i] = n;
		q.pb(i);
	}
	
	q.clear();
	R[n-1] = n;
	q.pb(n-1);
	for(int i = n-2; i >= 0; --i){
		while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
		if(!q.empty()) R[i] = q.back();
		else R[i] = n;
		q.pb(i);
	}
	

	up[n][0][0] = n;
	up[n][0][1] = n;
	for(int i = 0; i < n; ++i){
		if(H[L[i]] > H[R[i]]){
			up[i][0][0] = L[i];
			up[i][0][1] = R[i];
		}else{
			up[i][0][1] = L[i];
			up[i][0][0] = R[i];
		}
	}
	for(int j = 1; j < K; ++j){
		for(int i = 0; i <= n; ++i){
			up[i][j][0] = up[up[i][j - 1][0]][j - 1][0];
			up[i][j][1] = up[up[i][j - 1][1]][j - 1][1];
		}
	}

}
int minimum_jumps(int A, int B, int C, int D){
	int v = A, ans = 0;
	for(int j = K - 1; j >= 0; --j){
		if(H[up[v][j][0]] <= H[C]){
			ans += (1<<j);
			v = up[v][j][0];
		}
	}
	for(int j = K - 1; j >= 0; --j){
		if(H[up[v][j][1]] <= H[C]){
			ans += (1<<j);
			v = up[v][j][1];
		}
	}
	if(v == C) return ans;
	return -1;
}

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