Submission #975660

#	Time	Username	Problem	Language	Result	Execution time	Memory
975660		happy_node	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	3095 ms	21708 KiB

event2

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

const int MX=2e5+5, inf=1e9;

int N,K;
vector<pair<int,int>> v;

int dp[MX];
map<int,int> id;

int val[MX];
vector<pair<int,int>> op[MX];

bool vis[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>K;

	for(int i=0;i<N;i++) {
		int l,r;
		cin>>l>>r;
		v.push_back({l,r});
		id[l]=0;
		id[r]=0;
	}

	int z=1;
	for(auto &[x,y]:id) y=z++;

	for(auto &[l,r]:v) {
		l=id[l];
		r=id[r];
	}

	for(int i=0;i<N;i++) {
		op[v[i].first].push_back({v[i].second,i});
	}

	for(int i=2*N;i>=1;i--) {
		for(auto [j,ii]:op[i]) {
			dp[i]=max(dp[i],dp[j]+1);
		}
		dp[i]=max(dp[i],dp[i+1]);
	}

	val[0]=1e9;

	for(int i=2*N;i>=1;i--) {
		if(val[dp[i]]==0) {
			val[dp[i]]=i;
		}
	}

	vector<int> ans;

	set<int> pts;

	while(K>0) {
		int p=-1;
		for(int i=0;i<N;i++) {
			auto [l,r]=v[i];
			if(vis[i]) continue;
			if(r>val[K-1]) continue;
			auto it=pts.lower_bound(l);

			if(it==pts.end() || *it>=r) {
				p=i;
				break;
			}
		}

		if(p==-1) {
			cout<<-1<<endl;
			return 0;
		}

		ans.push_back(p+1);
		vis[p]=true;
		for(int k=v[p].first;k<v[p].second;k++) pts.insert(k);
		K--;
	}

	sort(ans.begin(),ans.end());

	for(auto x:ans) {
		cout<<x<<'\n';
	}

}

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