Submission #521610

#	Time	Username	Problem	Language	Result	Execution time	Memory
521610		eecs	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	166 ms	25528 KiB

event2

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

const int maxn = 200010;
int n, K, nxt[20][maxn], mn[maxn];
struct seg { int l, r; } p[maxn];
set<pair<int, int>> S;

int main() {
	scanf("%d %d", &n, &K);
	vector<int> V;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &p[i].l, &p[i].r);
		V.push_back(p[i].l), V.push_back(--p[i].r);
	}
	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());
	memset(mn, 0x3f, sizeof(mn));
	memset(nxt, 0x3f, sizeof(nxt));
	for (int i = 1; i <= n; i++) {
		p[i].l = lower_bound(V.begin(), V.end(), p[i].l) - V.begin() + 1;
		p[i].r = lower_bound(V.begin(), V.end(), p[i].r) - V.begin() + 1;
		mn[p[i].l] = min(mn[p[i].l], p[i].r);
	}
	for (int i = n << 1; i; i--) {
		nxt[0][i] = mn[i] = min(mn[i], mn[i + 1]);
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n << 1; j++) {
			if (nxt[i - 1][j] > 1e9) nxt[i][j] = nxt[i - 1][j];
			else nxt[i][j] = nxt[i - 1][nxt[i - 1][j] + 1];
		}
	}
	auto query = [&](int l, int r) {
		if (nxt[0][l] > r) return 0;
		int ans = 0;
		for (int i = 19; ~i; i--) if (nxt[i][l] <= r) {
			l = nxt[i][l] + 1, ans |= 1 << i;
		}
		return ans;
	};
	S.emplace(0, 0), S.emplace(n << 1 | 1, n << 1 | 1);
	int cur = query(1, n << 1);
	if (cur < K) puts("-1"), exit(0);
	for (int i = 1, cnt = 0; i <= n; i++) {
		auto nxt = S.lower_bound({p[i].l, 0}), pre = prev(nxt);
		if (pre->second >= p[i].l || p[i].r >= nxt->first) continue;
		int coef = query(pre->second + 1, p[i].l - 1) + query(p[i].r + 1,
			nxt->first - 1) - query(pre->second + 1, nxt->first - 1) + 1;
		if (cur + coef >= K) {
			cur += coef, S.emplace(p[i].l, p[i].r);
			printf("%d\n", i);
			if (++cnt == K) break;
		}
	}
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d %d", &n, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d %d", &p[i].l, &p[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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