Submission #976141

#	Time	Username	Problem	Language	Result	Execution time	Memory
976141		happy_node	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	3101 ms	32356 KiB

event2

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

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

int N,K;

vector<pair<int,int>> v;
map<int,int> id;
vector<pair<int,int>> cl[MX];

int dp[MX];
bool used[MX];

vector<int> ans;

int M;

set<int> st;

bool ok(int l, int r) {
	auto it=st.lower_bound(l);
	if(it==st.end() || *it>=r) return true;
	return false;
}

int f(int x) {
	vector<pair<int,int>> cur;

	auto [l,r]=v[x];
	if(!ok(l,r)) return -1e9;

	for(int k=l;k<r;k++) st.insert(k);
	cur.push_back({l,r});

	for(int k=1;k<=2*N;k++) {
		for(auto [j,id]:cl[k]) {
			if(ok(j,k)) {
				cur.push_back({j,k});
				for(int z=j;z<k;z++) st.insert(z);
			}
		}
	}

	for(auto [l,r]:cur) {
		for(int k=l;k<r;k++) st.erase(k);
	}

	return cur.size();
}

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++) {
		auto [l,r]=v[i];
		cl[r].push_back({l,i});
	}

	for(int i=0;i<N;i++) {
		if(ans.size()==K) break;
		if(f(i)+(int)ans.size()>=K) {
			auto [l,r]=v[i];
			for(int k=l;k<r;k++) st.insert(k);
			ans.push_back(i);
		}
	}

	if(ans.size()<K) {
		cout<<-1<<'\n';
		return 0;
	}
	
	sort(ans.begin(),ans.end());
	for(auto x:ans) {
		cout<<x+1<<" ";
	}
	cout<<'\n';
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:78:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |   if(ans.size()==K) break;
      |      ~~~~~~~~~~^~~
event2.cpp:86:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |  if(ans.size()<K) {
      |     ~~~~~~~~~~^~

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