Submission #1179051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179051		tamyte	Event Hopping (BOI22_events)	C++20	0 / 100	183 ms	18780 KiB

events

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct event {
	int s, e, i;
};


int main() {
	int n, q;
	cin >> n >> q;
	vector<event> a(n);
	vector<int> ptr(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i].s >> a[i].e;
		a[i].i = i;
	}
	// cout << endl;
	sort(begin(a), end(a), [&](const event x, const event y) {
		if (x.s != y.s) return x.s < y.s;
		return x.e > y.e;
	});
	for (int i = 0; i < n; ++i) {
		ptr[a[i].i] = i;
	}
	vector<vector<int>> lift(n, vector<int>(32, -1));
	for (int i = 0; i < n - 1; ++i) {
		if (a[i].e >= a[i + 1].s) {
			lift[i][0] = i + 1;
		}
	}
	for (int i = 1; i < 32; ++i) {
		for (int j = 0; j < n; ++j) {
			if (lift[j][i - 1] == -1) continue;
			lift[j][i] = lift[lift[j][i - 1]][i - 1];
		}
	}
	// for (int i = 0; i < 5; ++i) {
	// 	for (int j = 0; j < n; ++j) {
	// 		cout << lift[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
	// cout << endl;
	for (int i = 0; i < q; ++i) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		x = ptr[x];
		y = ptr[y];
		int end = a[y].s;
		int steps = 0;
		if (a[x].s >= a[y].e) {
			cout << "impossible\n";
			continue;
		}
		for (int j = 31; j >= 0; --j) {
			if (lift[x][j] == -1) continue;
			int tmp = lift[x][j];
			if (a[tmp].e < end) {
				steps += (1 << j);
				x = tmp;
			}
		}
		if (lift[x][0] == -1) {
			cout << "impossible\n";
			continue;
		}
		steps++;
		x = lift[x][0];
		if (a[x].e >= end) {
			cout << steps << "\n";
		} else {
			cout << "impossible\n";
		}
	}
}

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