Submission #1190148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190148		tamyte	Event Hopping (BOI22_events)	C++20	100 / 100	331 ms	21156 KiB

events

#include <bits/stdc++.h>

using namespace std;


struct RMQ {
	int n;
	vector<pair<int, int>> tree;
	RMQ(int n) {
		this->n = n;
		tree = vector<pair<int, int>>(4 * n + 1, {1e9 + 1, -1});
	}
	void update(int i, int l, int r, int qp, pair<int, int> val) {
		if (l == r) {
			tree[i] = min(tree[i], val);
			return;
		}
		int m = (l + r) / 2;
		if (qp <= m) {
			update(i * 2, l, m, qp, val);
		} else {
			update(i * 2 + 1, m + 1, r, qp, val);
		}
		tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
	}
	void update(int qp, pair<int, int> val) {
		update(1, 0, n - 1, qp, val);
	}
	pair<int, int> query(int i, int l, int r, int ql, int qr) {
		if (l > qr || ql > r) {
			return {1e9 + 1, -1};
		}
		if (ql <= l && r <= qr) {
			return tree[i];
		}
		int m = (l + r) / 2;
		return min(query(i * 2, l, m, ql, qr), 
			query(i * 2 + 1, m + 1, r, ql, qr));
	}
	pair<int, int> query(int ql, int qr) {
		return query(1, 0, n - 1, ql, qr);
	}
};



int main() {
	int n, q;
	cin >> n >> q;
	vector<int> pool;
	vector<int> s(n), e(n);
	RMQ seg(n * 2);
	for (int i = 0; i < n; ++i) {
		cin >> s[i] >> e[i];
		pool.push_back(e[i]);
		pool.push_back(s[i]);
	}
	sort(begin(pool), end(pool));
	pool.erase(unique(begin(pool), end(pool)), end(pool));
	for (int i = 0; i < n; ++i) {
		int r = lower_bound(begin(pool), end(pool), e[i]) - begin(pool);
		seg.update(r, {s[i], i});
	}
	vector<vector<int>> lift(n, vector<int>(20, -1));
	for (int i = 0; i < n; ++i) {
		int r = lower_bound(begin(pool), end(pool), e[i]) - begin(pool);
		int l = lower_bound(begin(pool), end(pool), s[i]) - begin(pool);
		auto p = seg.query(l, r);
		lift[i][0] = p.second;
	}
	for (int j = 1; j < 20; ++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];
		}
	}
	while (q--) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		if (x == y) {
			cout << "0\n";
			continue;
		}
		if (s[y] <= e[x] && e[x] <= e[y]) {
			cout << "1\n";
			continue;
		}
		int steps = 2;
		// cout << x << " " << y << " => ";
		// cout << "X = " << s[x] << " , " << e[x] << endl;
		// cout << "Y = " << s[y] << " , " << e[y] << endl;
		for (int j = 19; j >= 0; --j) {
			if (lift[y][j] == -1) {
				continue;
			}
			int ny = lift[y][j];
			// cout << ny << "\n";
			// cout << "CAND = " << s[ny] << " " << e[ny] << endl;
			if (e[x] < s[ny]) {
				y = ny;
				steps += (1 << j);
			} 
		}
		y = lift[y][0];
		// cout << x << " " << y << endl;
		if (y == -1) {
			cout << "impossible\n";
			continue;
		}
		// cout << "X = " << s[x] << " , " << e[x] << endl;
		// cout << "Y = " << s[y] << " , " << e[y] << endl;
		if (e[x] < s[y] || e[x] > e[y]) {
			cout << "impossible\n";
			continue;
		}
		cout << steps << "\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