Submission #528895

#	Time	Username	Problem	Language	Result	Execution time	Memory
528895		dutch	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	149 ms	16076 KiB

event2

#include <bits/stdc++.h>
using namespace std;
 
const int Z = 1e5+2, B = 17, INF = 2e9;
 
int N, K, L[Z], R[Z];
 
int p[Z][B];
 
set<array<int, 3>> s;
 
int solve(int i, int r) {
	int j = i, res = 1;
 
	for(int k = B; k--; )
		if(p[j][k] <= N && R[p[j][k]] <= r)
			j = p[j][k], res += 1<<k;
 
	return res;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> N >> K;
 
	array<int, 2> pts[N * 2];
 
	for(int i = 1; i <= N; ++i) {
		cin >> L[i] >> R[i];
		--R[i];
 
		pts[2 * i - 1] = {-L[i], +i};
		pts[2 * i - 2] = {-R[i], -i};
	}
 
	L[N+1] = R[N+1] = INF;
 
	sort(pts, pts + N * 2);
	int j = N + 1;
 
	p[0][0] = min_element(R+1, R+N+1) - R;
	p[N+1][0] = N+1;
 
	for(auto &[x, i] : pts) {
		if(i < 0)
			p[-i][0] = j;
		else if(R[i] < R[j])
			j = i;
	}
 
	for(j = 0; j + 1 < B; ++j)
		for(int i = 0; i <= N + 1; ++i)
			p[i][j+1] = p[p[i][j]][j];
 
	int sum = solve(0, INF - 1) - 1, req = K;
 
	if(sum < K) {
		cout << -1;
		return 0;
	}
 
	s.insert({L[0], 0, sum+1});
	s.insert({L[N+1], N+1, 0});
 
	for(int i = 1; i <= N && req; ++i) {
		auto fR = s.lower_bound({R[i] + 1});
		auto fL = prev(fR);
 
		if(R[(*fL)[1]] >= L[i]) continue;
 
		if(sum - (*fL)[2] + solve((*fL)[1], L[i]-1) + solve(i, (*fR)[0]-1) < K) continue;
		--req;
 
		array<int, 3> newL = *fL;
		newL[2] = solve((*fL)[1], L[i] - 1);
 
		int canDo = solve(i, (*fR)[0]-1);
 
		sum += newL[2] + canDo - (*fL)[2];
 
		s.erase(fL);
		s.insert(newL);
		s.insert({L[i], i, canDo});
 
		cout << i << '\n';
	}
}

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