Submission #745862

#	Time	Username	Problem	Language	Result	Execution time	Memory
745862		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	678 ms	132636 KiB

events

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

const int MAXN = 100001;
const int K = 20;

struct Node {
	Node *left, *right;
	int best = 0, start = INT_MAX, tl, tr;

	Node(int l_, int r_) : tl(l_), tr(r_) {}

	void expand() {
		if (left == nullptr) {
			int tm = (tl + tr) / 2;
			left = new Node(tl, tm);
			right = new Node(tm+1, tr);
		}
	}

	void upd(int l, int r, int val) {
		if (l > r) return;
		if (l == tl && r == tr) {
			best = max(best, val);
		} else {
			expand();
			int m = (tl + tr) / 2;
			left->upd(l, min(r, m), val);
			right->upd(max(l, m+1), r, val);
		}
	}

	void upd2(int l, int r, int val) {
		if (l > r) return;
		if (l == tl && r == tr) {
			start = min(start, val);
		} else {
			expand();
			int m = (tl + tr) / 2;
			left->upd2(l, min(r, m), val);
			right->upd2(max(l, m+1), r, val);
		}
	}

	int qry(int pos) {
		if (tl == tr) {
			return best;
		} else {
			expand();
			int m = (tl + tr) / 2;
			if (pos <= m) {
				return max(best, left->qry(pos));
			} else {
				return max(best, right->qry(pos));
			}
		}
	}

	int qry2(int pos) {
		if (tl == tr) {
			return start;
		} else {
			expand();
			int m = (tl + tr) / 2;
			if (pos <= m) {
				return min(start, left->qry2(pos));
			} else {
				return min(start, right->qry2(pos));
			}
		}
	}
};

int up[MAXN][K];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	Node *root = new Node(1, 2e9);
	vector<pair<int, int>> events(n+1);
	map<int, int> m;
	for (int i = 1; i <= n; i++) {
		cin >> events[i].first >> events[i].second;
		if (m.count(events[i].second)) {
			if (events[m[events[i].second]].first > events[i].first) {
				m[events[i].second] = i;
			}
		} else {
			m[events[i].second] = i;
		}
		root->upd(events[i].first, events[i].second, events[i].second);
		root->upd2(events[i].first, events[i].second, events[i].first);
	}
	for (int i = 1; i <= n; i++) {
		up[i][0] = m[root->qry(events[i].second)];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < K; j++) {
			up[i][j] = up[up[i][j-1]][j-1];
		}
	}
	while (q--) {
		int a, b; cin >> a >> b;
		int ans = 0;
		if (a == b) {
			cout << "0\n";
			continue;
		}
		if (events[a].second > events[b].second) {
			cout << "impossible\n";
			continue;
		}
		for (int it = 0; it < 100 && a != b; it++) {
			int best = -1, cur = 0;
			for (int i = 0; i < K && up[a][i]; i++) {
				if (events[up[a][i]].second <= events[b].first && up[a][i] != a && (i == 0 || up[a][i] != up[a][i-1])) {
					best = up[a][i];
					cur = 1 << i;
				}
			}
			if (best != -1) {
				a = best;
				ans += cur;
			}
		}
		if (a == b) {
			cout << ans << "\n";
		} else if (events[a].second == events[b].first || events[b].first < events[a].second) {
			cout << ans+1 << "\n";
		} else if (root->qry2(events[b].first) <= events[a].second) {
			cout << ans+2 << "\n";
		} else {
			cout << "impossible\n";
		}
	}
	return 0;
}

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