Submission #867721

#	Time	Username	Problem	Language	Result	Execution time	Memory
867721		TAhmed33	Event Hopping (BOI22_events)	C++98	10 / 100	416 ms	36688 KiB

events

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
int n, q;
vector <int> arr[MAXN];
vector <int> arr2[MAXN];
set <pair <int, int>> dd;
int par[MAXN];
int dep[MAXN], in[MAXN], out[MAXN];
int t = 0;
vector <int> adj[MAXN];
int val[MAXN];
void dfs (int pos) {
	in[pos] = ++t;
	for (auto j : adj[pos]) {
		dep[j] = 1 + dep[pos];
		dfs(j);
	}
	out[pos] = t;
}
bool flagged[MAXN]; int nxt[MAXN];
vector <vector <int>> events;
int main () {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		arr[i] = {l, r, i};
		events.push_back({l, 0, i});
		events.push_back({r, 1, i});
	}
	sort(events.begin(), events.end());
	reverse(events.begin(), events.end());
	while (!events.empty()) {
		int u = events.back()[0];
		vector <vector <int>> k;
		while (!events.empty() && events.back()[0] == u) {
			k.push_back(events.back());
			events.pop_back();
		}
		sort(k.begin(), k.end());
		reverse(k.begin(), k.end());
		while (!k.empty() && k.back()[1] == 0) {
			dd.insert({arr[k.back()[2]][1], k.back()[2]});
			k.pop_back();
		}
		vector <pair <int, int>> removals;
		while (!k.empty()) {
			dd.erase({k.back()[0], k.back()[2]});
			auto g = dd.lower_bound({k.back()[0], 0});
			if (g == dd.end()) {
				par[k.back()[2]] = -1;
				k.pop_back();
				continue;
			}
			par[k.back()[2]] = (*g).second;
			dd.insert({k.back()[0], k.back()[2]});
			k.pop_back();
		}
		for (auto i : removals) dd.erase(i);
	}
	for (int i = 1; i <= n; i++) {
		if (par[i] != -1 && par[par[i]] == i) {
			if (arr[par[i]][0] <= arr[i][0]) {
				flagged[i] = 1; nxt[i] = par[i];
			} else {
				flagged[par[i]] = 1; nxt[par[i]] = i;
			}
			par[par[i]] = -1; par[i] = -1; 
		}
	}
	for (int i = 1; i <= n; i++) if (par[i] != -1) {
		adj[par[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) if (par[i] == -1) dfs(i);
	while (q--) {
		int a, b;
		cin >> a >> b;
		if (a == b) {
			cout << "0\n";
			continue;
		}
		int ansss = 0; 
		if (flagged[a]) {
			a = nxt[a]; ansss++;
		}
		if (flagged[b]) {
			b = nxt[b]; ansss++;
		}
		if (a == b) {
			cout << ansss << '\n';
			continue;
		}
		if (arr[a][1] == arr[b][1]) {
			cout << ansss + 1 << '\n';
			continue;
		}
		if (in[a] > in[b] && out[a] <= out[b]) {
			cout << ansss + dep[a] - dep[b] << '\n';
		} else {
			cout << "impossible\n";
		}
	}
}

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