Submission #1173492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173492		pinbu	Event Hopping (BOI22_events)	C++20	100 / 100	140 ms	20476 KiB

events

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

const int N = 100005;

int n, q;
int num = -1;
array<int, 2> a[N];
int comp[N << 1];
struct SegmentTree {
	array<int, 2> val[1 << 19];
	void build(int id = 1, int l = 1, int r = num) {
		val[id] = {N << 4, N << 4};
		if (l == r) return;
		
		int mid = l + r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
	}
	void update(int i, int v, int idx, int id = 1, int l = 1, int r = num) {
		assert(l <= i && i <= r);
		val[id] = (!val[id][0]) ? array<int, 2>{v, idx} : min(val[id], {v, idx});
		if (l == r) return;
		
		int mid = l + r >> 1;
		i <= mid ? update(i, v, idx, id << 1, l, mid) : update(i, v, idx, id << 1 | 1, mid + 1, r);
	}
	array<int, 2> get(int Lf, int Rt, int id = 1, int l = 1, int r = num) {
		if (Lf <= l && r <= Rt) return val[id];
		
		int mid = l + r >> 1;
		array<int, 2> res = {N << 4, N << 4};
		if (Lf <= mid) res = min(res, get(Lf, Rt, id << 1, l, mid));
		if (Rt > mid) res = min(res, get(Lf, Rt, id << 1 | 1, mid + 1, r));
		return res;
	}
} T;
int prv[N][17], cost[N][17];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> q;
    for (int i = 1, l, r; i <= n; i++) {
    	cin >> l >> r;
    	a[i] = {l, r};
    	comp[++num] = l;
    	comp[++num] = r;
    }
    sort(comp, comp + 2 * n);
    num = unique(comp, comp + 2 * n) - comp;
    T.build();
    for (int i = 1; i <= n; i++) {
    	a[i][0] = lower_bound(comp, comp + num, a[i][0]) - comp + 1;
    	a[i][1] = lower_bound(comp, comp + num, a[i][1]) - comp + 1;
    	T.update(a[i][1], a[i][0], i);
    	// cerr << a[i][1] << ' ' << a[i][0] << ' ' << i << '\n';
    }
    for (int i = 1; i <= n; i++) {
    	prv[i][0] = T.get(a[i][0], a[i][1])[1];
    	// cerr << prv[i][0] << ' ';
    	cost[i][0] = i != prv[i][0];
    }
    // cerr << '\n';
    for (int k = 1; k < 17; k++) {
    	for (int i = 1; i <= n; i++) {
    		prv[i][k] = prv[prv[i][k - 1]][k - 1];
    		cost[i][k] = cost[i][k - 1] + cost[prv[i][k - 1]][k - 1];
    	}
    }
    while (q--) {
    	int s, e; cin >> s >> e;
    	if (s == e) {
    		cout << "0\n";
    		continue;
    	}
    	int ans = 0;
    	for (int k = 16; k >= 0; k--) {
    		if (a[prv[e][k]][0] > a[s][1]) {
    			ans += cost[e][k];
    			e = prv[e][k];
    		}
    	}
    	if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
    		cout << ans + 1 << '\n';
    		continue;
    	}
    	// cerr << e << " -> ";
    	ans += cost[e][0];
    	e = prv[e][0];
    	// cerr << e << '\n';
    	if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
    		cout << ans + 1 << '\n';
    		continue;
    	} else {
    		cout << "impossible\n";
    	}
    }
    
    return 0;
}

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