Submission #1210676

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

event2

#include <bits/stdc++.h>
using namespace std;
struct event {
	int l, r, id;
	bool operator == (const event e) {
		return id==e.id;
	}
};
int cnt(int N, vector<event> ev) {
	vector<int> ep[2*N];
	for(auto [l,r,i]: ev)
		ep[l].push_back(r);
	int dp[2*N+1];
	dp[2*N]=0;
	for(int i=2*N;i--;) {
		dp[i] = dp[i+1];
		for(auto j: ep[i])
			dp[i] = max(dp[i], dp[j] + 1);
	}
	return dp[0];
}
vector<event> fil(int l, int r, vector<event> ev) {
	vector<event> ans;
	for(auto [el, er, id]: ev)
		if(er <= l || el >= r)
			ans.push_back({el,er,id});
	return ans;
}
int main() {
	int n, k;
	cin >> n >> k;
	vector<event> v(n);
	vector<int> u;
	for(int i=0;i<n;i++) {
		cin >> v[i].l >> v[i].r;
		v[i].id = i;
		u.push_back(v[i].l);
		u.push_back(v[i].r);
	}
	sort(u.begin(),u.end());
	for(int i=0;i<n;i++) {
		v[i].l=lower_bound(u.begin(),u.end(),v[i].l)-u.begin();
		v[i].r=lower_bound(u.begin(),u.end(),v[i].r)-u.begin();
	}
	if(cnt(n,v) < k) {
		cout << -1;
		return 0;
	}
	vector<int> ans;
	while(v.size()) {
		pair<int,int> fst = {1e9,0};
		for(int i=-1;auto [l,r,id]:v)
			fst=min(fst,{id,++i});
		auto [l, r, i] = v[fst.second];
		vector<event> nw = fil(l, r, v);
		if(cnt(n,nw) >= k - 1) {
			v = nw;
			k--;
			ans.push_back(i);
		} else
			v.erase(find(v.begin(),v.end(),event{l,r,i}));
	}
	for(auto i: ans)
		cout << i+1 << "\n";
}

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