Submission #713616

#	Time	Username	Problem	Language	Result	Execution time	Memory
713616		HamletPetrosyan	Event Hopping (BOI22_events)	C++17	100 / 100	347 ms	27044 KiB

events

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

#define len(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define fr first
#define sc second

const int INF = 1e9;
const int N = 2e5 + 5, lN = 18;

int n, q;
pii a[N];
int par[N][lN];

vector<int> temp, ind;
map<int, int> mp;

pii t[4 * N];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v] = {INF, -1};
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v + 0, tl, tm + 0);
	build(2 * v + 1, tm + 1, tr);
	t[v] = {INF, -1};
}

void update(int v, int tl, int tr, int ind, int val, int i){
	if(tl == tr){
		t[v] = min(t[v], {val, i});
		return;
	}
	int tm = (tl + tr) / 2;
	if(ind <= tm) update(2 * v + 0, tl, tm + 0, ind, val, i);
	else update(2 * v + 1, tm + 1, tr, ind, val, i);
	t[v] = min(t[2 * v + 0], t[2 * v + 1]);
}

pii get(int v, int tl, int tr, int l, int r){
	if(l > r) return (pii){INF, -1};
	if(tl == l && tr == r) return t[v];
	int tm = (tl + tr) / 2;
	return min(get(2 * v + 0, tl, tm + 0, l, min(r, tm + 0)),
			   get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> a[i].fr >> a[i].sc;
		temp.push_back(a[i].fr);
		temp.push_back(a[i].sc);
		ind.push_back(i);
	}
	sort(all(temp));
	sort(all(ind), [](int i, int j){ return a[i] < a[j]; });

	int last = -1, cnt = 0;
	for(int i = 0; i < len(temp); i++){
		if(temp[i] == last) continue;
		cnt++;
		last = temp[i];
		mp[temp[i]] = cnt;
	}

	build(1, 1, cnt);
	for(int i = 0; i < n; i++){
		a[i].fr = mp[a[i].fr];
		a[i].sc = mp[a[i].sc];
		update(1, 1, cnt, a[i].sc, a[i].fr, i);
	}

	for(int i = 0; i < n; i++){
		pii h = get(1, 1, cnt, a[i].fr, a[i].sc);
		par[i][0] = (h.fr >= a[i].fr ? i : h.sc);
	}
	for(auto i : ind){
		for(int j = 1; j < lN; j++){
			par[i][j] = par[par[i][j - 1]][j - 1];
		}
	}

	int x, y;
	while(q--){
		cin >> x >> y;
		x--, y--;
		if(x == y){
			cout << "0\n";
			continue;
		}
		if(a[x].sc > a[y].sc){
			cout << "impossible\n";
			continue;
		}
		if(a[x].sc >= a[y].fr){
			cout << "1\n";
			continue;
		}

		int ans = 2;
		for(int i = lN - 1; ~i; i--){
			if(a[par[y][i]].fr <= a[x].sc) continue;
			ans += (1 << i);
			y = par[y][i];
		}
		if(a[par[y][0]].fr > a[x].sc){
			cout << "impossible\n";
			continue;
		}
		cout << ans << "\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