Submission #975658

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

event2

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

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

int N,K;
vector<pair<int,int>> vv;
vector<array<int,3>> 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=1;i<=N;i++) {
		int l,r;
		cin>>l>>r;
		v.push_back({r,l,i});
		vv.push_back({l,r});
		id[l]=0;
		id[r]=0;
	}

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

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

	for(auto [r,l,i]:v) {
		op[l].push_back({r,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 [r,l,ii]=v[i];
			if(vis[i]) continue;
			if(r>val[K-1]) continue;
			auto it=pts.lower_bound(l);
			if(it==pts.end() || *it>=r) {
				if(p==-1 || ii<v[p][2]) p=i;
			}
		}
		if(p==-1) {
			cout<<-1<<endl;
			return 0;
		}
		
		ans.push_back(v[p][2]);
		vis[p]=true;
		for(int k=v[p][1];k<v[p][0];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