제출 #1316189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316189		vlomaczk	Event Hopping (BOI22_events)	C++20	100 / 100	134 ms	17456 KiB

events

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 100'000;
vector<pair<int, int>> seg(M);
int base = 1<<19;
vector<int> T(2*base, -1);

int zminuj(int a, int b) {
	if(a==-1) return b;
	if(b==-1) return a;
	if(seg[a].first < seg[b].first) return a;
	return b;
}

int query(int a, int b) {
	if(a==b) return T[a+base];
	int res=-1;
	a+=base-1;
	b+=base+1;
	while(a/2!=b/2) {
		if(a%2==0) res = zminuj(T[a+1], res);
		if(b%2==1) res = zminuj(T[b-1], res);
		a/=2; b/=2;
	}
	return res;
}

void update(int x, int val) {
	x += base;
	T[x] = zminuj(T[x], val);
	x/=2;
	while(x>0) {
		T[x] = zminuj(T[x+x], T[x+x+1]);
		x/=2;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, q;
	cin >> n >> q;
	ll inf = 1e9;
	int maxlog = 16;
	vector<vector<int>> jump(n, vector<int>(maxlog+1));
	vector<int> XY;
	for(int i=0; i<n; ++i) {
		cin >> seg[i].first >> seg[i].second;
		XY.push_back(seg[i].first);
		XY.push_back(seg[i].second);
	}
	sort(XY.begin(), XY.end());
	for(int i=0; i<n; ++i) {
		update(lower_bound(XY.begin(), XY.end(), seg[i].second) - XY.begin(), i);
	}
	for(int i=0; i<n; ++i) {
		jump[i][0] = query(lower_bound(XY.begin(), XY.end(), seg[i].first) - XY.begin(), lower_bound(XY.begin(), XY.end(), seg[i].second) - XY.begin());
		// cout << i << ": " << jump[i][0] << "\n";
	}
	for(int j=1; j<=maxlog; ++j) {
		for(int i=0; i<n; ++i) {
			jump[i][j] = jump[jump[i][j-1]][j-1];
		}
	}
	while(q--) {
		int a, b;
		cin >> a >> b;
		--a;--b;
		if(a==b) {
			cout << "0\n";
			continue;
		}
		int res = 0;
		for(int i=maxlog; i>=0; --i) {
			if(seg[a].second < seg[jump[b][i]].first) {
				res += 1<<i;
				b=jump[b][i];
			}
		}
		if(seg[b].first <= seg[a].second && seg[a].second <= seg[b].second) cout << res+1 << "\n";
		else if(seg[jump[b][0]].first <= seg[a].second && seg[a].second <= seg[jump[b][0]].second) cout << res+2 << "\n";
		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