제출 #853413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853413		vjudge1	Event Hopping (BOI22_events)	C++17	20 / 100	124 ms	22776 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

bool can_reach(int i, int j, vector<int>& S, vector<int>& E){
	if(S[j] <= E[i] && E[i] <= E[j]) return true;
	else return false;
}

void solve(){
	int N, Q; cin >> N >> Q;
	vector<int> E(N);
	vector<int> original_start(N);
	vector<pair<int, int>> S(N);
	for(int i = 0; i < N; i++) {cin >> S[i].first >> E[i]; S[i].second = i; original_start[i] = S[i].first;}
	vector<pair<int, int>> adj(N); //Order by E[i], then by i.
	set<pair<int,int>> s;
	sort(S.begin(), S.end());
	for(pair<int, int> p : S){
		while((int)s.size() > 0 && (*s.begin()).first < p.first){
			pair<int, int> pr = *s.begin(); s.erase(s.begin());
			pair<int, int> pr1 = {-1, -1};
			if((int)s.size() > 0) pr1 = *s.rbegin();
			adj[pr.second] = max(pr1, pr);
		}
		s.insert({E[p.second], p.second});
	}
	while((int)s.size() > 0){
		pair<int, int> pr = *s.begin(); s.erase(s.begin());
		pair<int, int> pr1 = {-1, -1};
		if((int)s.size() > 0) pr1 = *s.rbegin();
		adj[pr.second] = max(pr1, pr);
	}
	vector<vector<pair<int, int>>> dp(20, vector<pair<int, int>>(N));
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) dp[k][i] = adj[i];
			else{
				dp[k][i] = dp[k-1][dp[k-1][i].second];
			}
		}
	}
	while(Q--){
		int s, e; cin >> s >> e; s--; e--;
		if(s == e){
			cout << 0 << endl;
			continue;
		}
		int ans = 0;
		for(int k = 19; k >= 0; k--){
			pair<int, int> pr = {E[e], e};
			if(dp[k][s] < pr){
				s = dp[k][s].second;
				ans += (1 << k);
			}
		}
		ans++;
		if(can_reach(s, e, original_start, E)) cout << ans << endl;
		else cout << "impossible" << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30