Submission #828978

#	Time	Username	Problem	Language	Result	Execution time	Memory
828978		QwertyPi	Event Hopping (BOI22_events)	C++14	30 / 100	467 ms	67872 KiB

events

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 2e5 + 11;
struct event{
	int s, e, i;
};

event a[N];
int p[N], R[N];
int lift[N][20];
int n, q; 

struct SegTree{
	int t[N << 2];
	void update(int p, int val, int v = 0, int l = 0, int r = n * 2){
		if(l == r) t[v] = min(t[v], val);
		else {
			int m = (l + r) / 2;
			if(p <= m) update(p, val, v * 2 + 1, l, m);
			else update(p, val, v * 2 + 2, m + 1, r);
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	int query_suff_min(int p, int v = 0, int l = 0, int r = n * 2){
		if(l == r) return t[v];
		int m = (l + r) / 2;
		if(p <= m) return min(query_suff_min(p, v * 2 + 1, l, m), t[v * 2 + 2]);
		else return query_suff_min(p, v * 2 + 2, m + 1, r);
	}
} ST;
int32_t main(){
	fill(ST.t, ST.t + (N << 2), 1 << 30);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		int s, e; cin >> s >> e; a[i] = {s, e, i};
	}
	{
		set<int> S; map<int, int> mp;
		for(int i = 1; i <= n; i++) S.insert(a[i].s), S.insert(a[i].e);
		int id = 1; for(auto i : S) mp[i] = id++;
		for(int i = 1; i <= n; i++) a[i].s = mp[a[i].s], a[i].e = mp[a[i].e];
	}
	sort(a + 1, a + n + 1, [](event u, event v){ return u.e < v.e; });
	R[n] = n; for(int i = n - 1; i >= 1; i--) R[i] = a[i].e == a[i + 1].e ? R[i + 1] : i;

	for(int i = 1; i <= n; i++){
		for(int j = R[i - 1] + 1; j <= R[i]; j++) ST.update(a[j].e, a[j].s);
		lift[a[i].s][0] = ST.query_suff_min(a[i].s);
		for(int j = 1; j < 20; j++) lift[a[i].s][j] = lift[lift[a[i].s][j - 1]][j - 1];
	}
	for(int i = 1; i <= n; i++) p[a[i].i] = i;
	for(int i = 0; i < q; i++){
		int u, v; cin >> u >> v; u = p[u], v = p[v];
		if(a[u].e > a[v].e){
			cout << "impossible" << endl;
			continue;
		}
		if(u == v){
			cout << 0 << endl;
			continue;
		}
		if(a[v].s <= a[u].e && a[u].e <= a[v].e){
			cout << 1 << endl;
			continue;
		}
		int ans = 0, x = a[v].s;
		for(int j = 19; j >= 0; j--){
			if(a[u].e < lift[x][j]) ans += (1 << j), x = lift[x][j];
		}
		cout << (ans >= (1 << 19) ? "impossible" : to_string(ans + 2)) << endl;
	}
}

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