Submission #1179106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179106		tamyte	Event Hopping (BOI22_events)	C++20	100 / 100	154 ms	22272 KiB

events

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

struct event {
	int s, e, i;
};
const int N = 4e5;
struct rmq {
	vector<pair<int, int>> tree;
	
	void update(int v, int l, int r, int qpos, pair<int, int> value) {
		if (l == r) {
			tree[v] = min(tree[v], value);
			return;
		}
		int m = (l + r) / 2;
		if (qpos <= m) {
			update(v * 2, l, m, qpos, value);
		} else {
			update(v * 2 + 1, m + 1, r, qpos, value);
		}
		tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
	}
	pair<int, int> query(int v, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return {1e9 + 1, -1};
		if (ql <= l && r <= qr) return tree[v];
		int m = (l + r) / 2;
		return min(query(v * 2, l, m, ql, qr), query(v * 2 + 1, m + 1, r, ql, qr));
	}
	
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<pair<int, int>> a(n);
	vector<int> pool;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].first >> a[i].second;
		pool.push_back(a[i].second);
	}
	sort(begin(pool), end(pool));
	pool.erase(unique(begin(pool), end(pool)), end(pool));
	rmq seg;
	for (int i = 0; i <= N; ++i) {
		seg.tree.push_back({1e9 + 1, -1});
	}
	for (int i = 0; i < n; ++i) {
		int id = lower_bound(begin(pool), end(pool), a[i].second) - begin(pool);
		seg.update(1, 0, n - 1, id, {a[i].first, i});
	}
	vector<vector<int>> lift(n, vector<int>(32, -1));
	for (int i = 0; i < n; ++i) {
		int l = lower_bound(begin(pool), end(pool), a[i].first) - begin(pool);
		int r = lower_bound(begin(pool), end(pool), a[i].second) - begin(pool);
		pair<int, int> val = seg.query(1, 0, n - 1, l, r);
		// cout << a[i].first << " " << a[i].second << " : " << val.first << " " << val.second << endl;
		lift[i][0] = val.second;
	}
	for (int j = 1; j < 32; ++j) {
		for (int i = 0; i < n; ++i) {
			if (lift[i][j - 1] == -1) continue;
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	for (int j = 0; j <= 3; ++j) {
	// 		cout << lift[i][j] << " ";
	// 	}
	// 	cout << "\n";
	// }
	// cout << "\n";
	for (int i = 0; i < q; ++i) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		if (x == y || (a[y].first <= a[x].second && a[x].second <= a[y].second)) {
			if (x == y) {
				cout << "0\n";
			} else {
				cout << "1\n";
			}
			continue;
		}
		int steps = 1;
		// cout << a[x].second << " " << a[y].first << "\n";
		for (int j = 31; j >= 0; --j) {
			if (lift[y][j] == -1) continue;
			if (a[x].second < a[lift[y][j]].first) {
				steps += (1 << j);
				y = lift[y][j];
			}
		}
		if (lift[y][0] == -1) {
			cout << "impossible\n";
			continue;
		}
		y = lift[y][0];
		if (a[x].second < a[y].first || a[x].second > a[y].second) {
			cout << "impossible\n";
		} else {
			cout << steps + 1 << "\n";
		}
	}
}

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