Submission #1246267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246267		trideser	Event Hopping (BOI22_events)	C++20	0 / 100	1595 ms	1456 KiB

events

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

int main() {
	int N, Q;
	cin >> N >> Q;
	vector<pair<int, int>> events(N);
	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		events[i] = make_pair(a, b);
	}
	//vector<pair<int, int>> events2 = events;
	//sort(events2.begin(), events2.end());
	vector<int> optimal(N);
	for(int i = 0; i < N; i++) {
		int opt = -1;
		for(int j = 0; j < N; j++) {
			//cout << events[i].first << " - " << events[i].second << " : ";
			//cout << events[j].first << " - " << events[j].second << "\n";
			//cout << (events[j].first < events[i].first) << (events[j].second > events[i].first) << "\n";
			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)) {
				//cout << "OPT\n";
				opt = j;
			}
		}

		optimal[i] = opt;
	}
	//vector<pair<int, int>> goodev;
	/*for(pair<int, int> p : events2) {
		while(!goodev.empty() && (goodev.back().first == p.first)) {
			goodev.pop_back();
		}
		if(goodev.empty() || goodev.back().second < p.second)
			goodev.push_back(p);
	}
	for(pair<int, int> p : goodev)
		cout << p.first << " " << p.second << "\n";*/
	/*for(int a : optimal)
		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].first) {
			cout << "impossible\n";
			continue;
		}
		int ret = 0;
		int currentE = b;
		while(currentE != -1 && events[currentE].first > events[a].second) {
			//cout << "\t" << currentE << "\n";
			currentE = optimal[currentE];
			ret++;
		}
		if(currentE == -1)
			cout << "impossible\n";
		else
			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