Submission #1210723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210723		PenguinsAreCute	Event Hopping 2 (JOI21_event2)	C++20	0 / 100	59 ms	2744 KiB

event2

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k;
	cin >> n >> k;
	int l[n], r[n];
	vector<int> u;
	for(int i=0;i<n;i++) {
		cin >> l[i] >> r[i];
		u.push_back(l[i]);
		u.push_back(r[i]);
	}
	sort(u.begin(),u.end());
	for(int i=0;i<n;i++) {
		l[i]=lower_bound(u.begin(),u.end(),l[i])-u.begin();
		r[i]=lower_bound(u.begin(),u.end(),r[i])-u.begin();
	}
	int dp[2*n+1];
	dp[2*n]=0;
	int p=n-1;
	for(int i=2*n;i--;) {
		dp[i] = dp[i+1];
		if(p!=-1&&i==l[p])
			dp[i] = max(dp[i], dp[r[p--]] + 1);
	}
	if(dp[0] < k) {
		cout << -1;
		return 0;
	}
	int i=0;
	while(k) {
		if(dp[r[i]] >= k - 1) {
			cout << i+1 << "\n";
			i = lower_bound(l,l+n,r[i])-l;
			k--;
		} else
			i++;
	}
}

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