Submission #853503

#	Time	Username	Problem	Language	Result	Execution time	Memory
853503		esomer	Event Hopping (BOI22_events)	C++17	100 / 100	491 ms	47156 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

struct segTree{
	vector<pair<int, int>> mn;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		mn.assign(2 * sz, {2e9, 2e9});
	}
	void set(int i, pair<int, int> val, int x, int lx, int rx){
		if(rx - lx == 1){
			mn[x] = val;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set(i, val, 2 * x + 1, lx, m);
		else set(i, val, 2 * x + 2, m, rx);
		mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
	}
	void set(int i, pair<int, int> val){
		set(i, val, 0, 0, sz);
	}
	pair<int, int> calc(int l, int r, int x, int lx, int rx){
		if(lx >= l && rx <= r) return mn[x];
		else if(lx >= r || rx <= l) return {2e9, 2e9};
		int m = (lx + rx) / 2;
		pair<int, int> p1 = calc(l, r, 2 * x + 1, lx, m);
		pair<int, int> p2 = calc(l, r, 2 * x + 2, m, rx);
		return min(p1, p2);
	}
	pair<int, int> calc(int l, int r){
		return calc(l, r, 0, 0, sz);
	}
};

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> S(N);
	vector<int> all;
	for(int i = 0; i < N; i++) {cin >> S[i] >> E[i]; all.push_back(S[i]); all.push_back(E[i]);}
	sort(all.begin(), all.end());
	int curr = 0;
	int lst_x = -1;
	map<int, int> frst;
	map<int, int> lst;
	for(int x : all){
		bool fst = 0;
		if(x != lst_x) fst = 1;
		lst_x = x;
		lst[x] = curr;
		if(fst) frst[x] = curr;
		curr++;
	}
	map<int, int> add;
	segTree st; st.init(2 * N);
	for(int i = 0; i < N; i++){
		st.set(frst[E[i]] + add[E[i]], {S[i], i});
		add[E[i]]++;
	}
	vector<pair<int, int>> adj(N); //Order by E[i], then by i.
	for(int i = 0; i < N; i++){
		adj[i] = st.calc(frst[S[i]], lst[E[i]] + 1);
	}
	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];
			}
		}
	}
	// for(int i = 0; i < N; i++){
	// 	cout << "i " << i << " adj " << adj[i].first << " " << adj[i].second << endl;
	// }
	// for(int k = 0; k < 3; k++){
	// 	cout << "k " << k << endl;
	// 	for(int i = 0; i < N; i++){
	// 		cout << "i " << i << " " << dp[k][i].first << " " << dp[k][i].second << endl;
	// 	}
	// }
	while(Q--){
		int s, e; cin >> s >> e; s--; e--;
		if(s == e){
			cout << 0 << endl;
			continue;
		}else if(can_reach(s, e, S, E)){
			cout << 1 << endl;
			continue;
		}
		int orge = e;
		int ans = -1;
		int curr = 0;
		for(int k = 19; k >= 0; k--){
			if(dp[k][e].first > E[s]){
				e = dp[k][e].second;
				curr += (1 << k);
			}else ans = curr + (1 << k);
		}
		if(ans != -1 && E[s] <= E[orge]) cout << ans + 1 << endl;
		else cout << "impossible" << endl;
	}
}

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

	solve();
}

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