Submission #1246318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246318		trideser	Event Hopping (BOI22_events)	C++20	100 / 100	248 ms	21560 KiB

events

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

int main() {
	int N, Q;
	cin >> N >> Q;
	vector<pair<int, int>> events(N);
	vector<int> numbers(2 * N);
	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		events[i] = make_pair(a, b);
		numbers[2 * i] = a;
		numbers[2 * i + 1] = b;
	}
	sort(numbers.begin(), numbers.end());
	unordered_map<int, int> mp;
	int ix = -1;
	int lst = -1;
	for(int a : numbers) {
		if(a != lst) {
			ix++;
			lst = a;
			mp[a] = ix;
		}
	}
	/*for(auto it : mp)
		cout << it.first << " " << it.second << "\n";
	cout << "\n";*/
	int s = 1;
	int d = 0;
	while(s < mp.size()) {
		s *= 2;
		d++;
	}
	vector<pair<int, int>> tree(2 * s, make_pair(0x7fffffff, -1));

	for(int i = 0; i < N; i++) {
		pair<int, int> p = events[i];
		if(p.first < tree[s + mp[p.second]].first) {
			tree[s + mp[p.second]] = make_pair(p.first, i);
		}
		//tree[s + mp[p.second]] = min(tree[s + mp[p.second]], p.first);
	}
	for(int i = s - 1; i > 0; i--) {
		tree[i] = min(tree[2 * i], tree[2 * i + 1]);
	}
	/*for(int a : tree)
		cout << a << " ";
	cout << "\n";*/
	vector<int> optimal(N);
	for(int i = 0; i < N; i++) {
		pair<int, int> opt = make_pair(0x7fffffff, -1);
		int a = mp[events[i].first];
		int b = mp[events[i].second];
		int l = 1;
		int r = 1;
		for(int i = d - 1; i >= 0; i--) {
			bool bb = l != r;
			if((1 << i) & a) {
				l = 2 * l + 1;
			}
			else {
				if(bb) {
					opt = min(opt, tree[2 * l + 1]);
				}
				l = 2 * l;
			}
			if((1 << i) & b) {
				if(bb)
					opt = min(opt, tree[2 * r]);
				r = 2 * r + 1;
			}
			else {
				r = 2 * r;
			}
		}
		opt = min(opt, tree[l]);
		opt = min(opt, tree[r]);
		/*opt = -1;
		for(int j = 0; j < N; j++) {
			if(events[j].first < events[i].first &&
					events[j].second >= events[i].first &&
					events[j].second <= events[i].second &&
					(opt == -1 || events[j].first < events[opt].first)) {
				opt = j;
			}
		}*/
		if(events[opt.second].first < events[i].first)
			optimal[i] = opt.second;
		else
			optimal[i] = -1;
	}

	/*for(int a : optimal)
		cout <<a << " ";
	cout << "\n";*/

	vector<vector<int>> jumps;
	jumps.push_back(optimal);
	bool bb = true;
	while(bb) {
		bb = false;
		vector<int> cur(N);
		for(int i = 0; i < N; i++) {
			if(jumps.back()[i] == -1)
				cur[i] = -1;
			else{
				cur[i] = jumps.back()[jumps.back()[i]];
				bb = true;
			}
		}
		jumps.push_back(cur);
	}
	/*for(vector<int> vec : jumps) {
		for(int a : vec)
			cout << a << " ";
		cout << "\n";
	}*/
	for(int i = 0; i < Q; i++) {
		int a, b;
		cin >> a >> b;
		if(a == b) {
			cout << "0\n";
			continue;
		}
		a--;
		b--;
		if(events[a].second > events[b].second) {
			cout << "impossible\n";
			continue;
		}
		if(events[a].second >= events[b].first) {
			cout << "1\n";
			continue;
		}
		int ret = 0;
		int currentE = b;
		bool possible = false;
		/*while(currentE != -1 && events[currentE].first > events[a].second) {
			//cout << "\t" << currentE << "\n";
			currentE = optimal[currentE];
			ret++;
		}*/
		
		for(int i = jumps.size() - 1; i >= 0; i--) {
			if(jumps[i][currentE] == -1)
				continue;
			if(events[jumps[i][currentE]].first > events[a].second) {
				currentE = jumps[i][currentE];
				ret += (1 << i);
			}
			else {
				possible = true;
			}
		}
		if(!possible)
			cout << "impossible\n";
		else
			cout << ret + 2 << "\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