제출 #587751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587751		M_W	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4022 ms	11540 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int dist[200002];
int l[200002], r[200002];
vector<pair<int, int>> v;
int N;

void init(int N_tmp, vector<int> H) {
	N = N_tmp;
	for(int i = 0; i < N; i++){
		v.push_back({H[i], i + 1});
	}
	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});
		if(it != v2.end()) r[x] = (*it).first;
		if(it != v2.begin()){
			it--;
			l[x] = (*it).first;
		}
		v2.insert({tmp, x});
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	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});
	}
	return ans == 1000000000 ? -1 : ans;
}

• 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