Submission #587787

#	Time	Username	Problem	Language	Result	Execution time	Memory
587787		M_W	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1119 ms	48064 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int dist[200002];
int l[200002], r[200002];
vector<pair<int, int>> v;
int N; bool st1 = true;
int up[200002][21], dis[200002][21];
vector<int> H;

void init(int N_tmp, vector<int> H_tmp) {
	N = N_tmp; H = H_tmp;
	for(int i = 0; i < N; i++){
		v.push_back({H[i], i + 1});
		if(H[i] != i + 1) st1 = false;
	}
	sort(v.begin(), v.end(), greater<pair<int, int>>());
	set<pair<int, int>> v2;
	for(auto [x, tmp] : v){
		if(v2.empty()){
			v2.insert({tmp, x});
			continue;
		}
		auto it = v2.lower_bound({tmp, 0});
		// printf(">> %d %d : %d %d\n", x, tmp, (*it).first, (*it).second);
		if(it != v2.end()) r[x] = (*it).second;
		if(it != v2.begin()){
			it--;
			l[x] = (*it).second;
		}
		
		if((r[x] == 0 && l[x] != 0) || (l[x] < r[x] && l[x] != 0)) up[x][0] = l[x];
		else if(l[x] == 0 || r[x] < l[x]) up[x][0] = r[x];
		dis[x][0] = 1;
		
		int i = 1;
		if(l[x] != 0 && r[x] != 0){
			up[x][1] = max(l[x], r[x]);
			dis[x][1] = 1; i++;
		}
		
		// printf("!!! %d : %d %d: %d %d\n", x, l[x], r[x], up[x][0], up[x][1]);
		
		for(; i <= 20; i++){
			up[x][i] = up[up[x][i - 1]][i - 1];
			dis[x][i] = dis[up[x][i - 1]][i - 1] + dis[x][i - 1];
		}
		
		v2.insert({tmp, x});
	}
//	for(int i = 1; i <= N; i++){
//		for(int j = 0; j <= 3; j++){
//			printf("up %d %d: %d\n", i, j, up[j][i]);
//		}
//	}
}

int minimum_jumps(int A, int B, int C, int D) {
	if(st1) return C - B;
	
	if(A == B && C == D){
		B = H[B], C = H[C];
		int ans = 0;
		for(int i = 20; i >= 0; i--){
			if(up[B][i] != 0 && up[B][i] < C){
				// printf("%d ==> %d, %d\n", B, up[B][i], C);
				ans += dis[B][i];
				B = up[B][i];
			}
		}
		// printf(">> %d %d\n", up[B][0], B);
		if(up[B][0] != C) return -1;
		return ans + dis[B][0];
	}
	
	int ans = 1000000000; A++; B++; C++; D++;
	for(int i = 0; i <= N; i++) dist[i] = 1000000000;
	for(auto [x, idx]: v){
		if(idx >= C && idx <= D) dist[x] = 0;
		if(idx >= A && idx <= B) ans = min({ans, dist[l[x]] + 1, dist[r[x]] + 1});
		
		dist[x] = min({dist[x], dist[l[x]] + 1, dist[r[x]] + 1});
		// printf(">> %d (%d, %d) : %d %d\n", x, l[x], r[x], dist[l[x]], dist[r[x]]);
	}
	return ans == 1000000000 ? -1 : ans;
}

• 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