Submission #1226242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226242		eriksuenderhauf	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	171 ms	21468 KiB

event2

#include <bits/stdc++.h>
using namespace std;
const int LG = 18;

int main() {
	int n, k; cin >> n >> k;
	vector<int> p(2 * n);
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		p[2 * i] = a[i].first;
		p[2 * i + 1] = a[i].second;
	}
	sort(p.begin(), p.end());
	p.erase(unique(p.begin(), p.end()), p.end());
	int m = (int)p.size();
	vector<vector<int>> jmp(LG, vector<int>(m + 1, m));
	for (int i = 0; i < n; i++) {
		int l = lower_bound(p.begin(), p.end(), a[i].first) - p.begin();
		int r = lower_bound(p.begin(), p.end(), a[i].second) - p.begin();
		a[i] = {l, r};
		jmp[0][l] = min(jmp[0][l], r);
	}
	for (int j = m - 2; j >= 0; j--)
		jmp[0][j] = min(jmp[0][j], jmp[0][j + 1]);
	for (int i = 1; i < LG; i++)
		for (int j = 0; j < m; j++)
			jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];
	auto eval = [&](int l, int r) {
		int res = 0;
		for (int i = LG - 1; i >= 0; i--) {
			if (jmp[i][l] <= r) {
				res += 1 << i;
				l = jmp[i][l];
			}
		}
		return res;
	};

	int cur = eval(0, m - 1);
	if (cur < k) {
		cout << "-1\n";
		return 0;
	}
	set<pair<int, int>> used;
	used.insert({0, 0});
	used.insert({m - 1, m - 1});
	for (int i = 0; i < n; i++) {
		auto it = used.lower_bound({a[i].second, 0});
		int l = prev(it)->second;
		int r = it->first;
		if (a[i].first < l) {
			continue;
		}
		int cnt = cur - eval(l, r) + eval(l, a[i].first) + 1 + eval(a[i].second, r);
		if (cnt >= k) {
			cout << i + 1 << "\n";
			cur = cnt;
			used.insert(a[i]);
		}
		if ((int)used.size() - 2 >= k) {
			break;
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61