Submission #791991

#	Time	Username	Problem	Language	Result	Execution time	Memory
791991		ToniB	Event Hopping (BOI22_events)	C++17	0 / 100	163 ms	27060 KiB

events

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 2;
const int OFF = 1 << 19;
const int LOG = 17;

int n, q, s[MAXN], e[MAXN], bl[MAXN][LOG];
set<pair<int, int> > st;
vector<pair<int, bool> > v[MAXN];
pair<int, int> tour[OFF];

void upd(int x, int l, int r, int i, pair<int, int> val, bool keep = 0){
	if(i < l || i > r) return ;
	if(l == r){
		if(keep) tour[x] = min(tour[x], val);
		else tour[x] = val;
		return ;
	}
	int mid = (l + r) >> 1;
	upd(x * 2 + 1, l, mid, i, val, keep);
	upd(x * 2 + 2, mid + 1, r, i, val, keep);
	tour[x] = min(tour[x * 2 + 1], tour[x * 2 + 2]);
}
pair<int, int> f(int x, int l, int r, int ql, int qr){
	if(ql > r || l > qr) return {1e9, 0};
	if(ql <= l && r <= qr) return tour[x];
	int mid = (l + r) >> 1;
	return min(f(x * 2 + 1, l, mid, ql, qr), f(x * 2 + 2, mid + 1, r, ql, qr));
}

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

	cin >> n >> q;
	unordered_map<int, int> um;
	vector<int> cmp;
	for(int i = 0; i < n; ++i){
		cin >> s[i] >> e[i];
		cmp.push_back(s[i]);
		cmp.push_back(e[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	for(int i = 0; i < (int)cmp.size(); ++i){
		um[cmp[i]] = i;
	}
	for(int i = 0; i < n; ++i){
		s[i] = um[s[i]]; e[i] = um[e[i]];
		v[s[i]].push_back({i, 0});
		v[e[i]].push_back({i, 1});
	}
	for(int i = 0; i < 2 * n; ++i){
		upd(0, 0, 2 * n - 1, i, {1e9, 0});
	}
	for(int i = 0; i < n; ++i){
		upd(0, 0, 2 * n - 1, e[i], {s[i], i}, 1);
	}
	for(int i = 0; i < n; ++i){
		bl[i][0] = f(0, 0, 2 * n - 1, s[i], e[i]).second;
		cout << i << " -> " << bl[i][0] << "\n";
	}
	
	for(int j = 1; j < LOG; ++j){
		for(int i = 0; i < n; ++i){
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}
	while(q--){
		int qs, qe; cin >> qs >> qe, --qs, --qe;
		if(qs == qe){
			cout << "0\n"; continue;
		} else if(s[qe] <= e[qs] && e[qs] <= e[qe]){
			cout << "1\n"; continue;
		} else if(e[qs] > e[qe]){
			cout << "impossible\n"; continue;
		}

		int ret = 0;
		for(int i = LOG - 1; i >= 0; --i){
			int idx = bl[qe][i];
			if(e[qs] < s[idx]){
				qe = idx;
				ret += 1 << i;
			}
		}
		qe = bl[qe][0]; ++ret;

		if(e[qs] < s[qe]) cout << "impossible\n";
		else{
			assert(s[qe] <= e[qs] && e[qs] <= e[qe]);
			cout << ret + 1 << "\n";
		}
	}
	return 0;
}

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