Submission #867734

#	Time	Username	Problem	Language	Result	Execution time	Memory
867734		TAhmed33	Event Hopping (BOI22_events)	C++98	0 / 100	1584 ms	16840 KiB

events

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int bad = 1e9;
struct SegmentTree {
	int tree[2 * MAXN];
	void init () {
		for (auto &i : tree) i = bad;
	}
	void update (int l, int r, int a, int b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			tree[node] = min(tree[node], b);
			return;
		}
		update(l, mid, a, b, tl);
		update(mid + 1, r, a, b, tr);
		tree[node] = min(tree[tl], tree[tr]);
	}
	int get (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return bad;
		if (l >= a && r <= b) return tree[node];
		return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
} cur;
vector <int> adj[MAXN];
vector <int> arr[MAXN];
vector <int> d;
int dp[MAXN];
vector <vector <int>> events;
int idxx[MAXN];
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		arr[i] = {l, r, i};
		d.push_back(l); d.push_back(r);
	}
	sort(d.begin(), d.end()); d.resize(unique(d.begin(), d.end()) - d.begin());
	for (int i = 1; i <= n; i++) {
		arr[i][0] = lower_bound(d.begin(), d.end(), arr[i][0]) - d.begin();
		arr[i][1] = lower_bound(d.begin(), d.end(), arr[i][1]) - d.begin();
		arr[i][0]++; arr[i][1]++;
	}
	sort(arr + 1, arr + n + 1, [] (vector <int> &a, vector <int> &b) {
		return a[1] == b[1] ? a[0] < b[0] : a[1] < b[1];
	});
	for (int i = 1; i <= n; i++) idxx[arr[i][2]] = i;
	while (q--) {	
		int a, b;
		cin >> a >> b; 
		if (a == b) {
			cout << "0\n";
			continue;
		}
		cur.init();
		int ans = -1;
		for (int i = idxx[a]; i <= idxx[b]; i++) {
			int l = arr[i][0], r = arr[i][1], idx = arr[i][2];
			if (idx == a) {
				cur.update(1, MAXN, r, 0, 1);
				continue;
			}
			if (idx == b) {
				ans = cur.get(1, MAXN, l, r, 1);
				break;
			}
			int x = cur.get(1, MAXN, l, r, 1);
			cur.update(1, MAXN, r, x + 1, 1);
		}		
		ans++;
		if (ans > n) {
			cout << "impossible\n";
		} else {
			cout << ans << '\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