Submission #976132

#	Time	Username	Problem	Language	Result	Execution time	Memory
976132		happy_node	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	3 ms	11612 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;

bool ok(int l, int r) {
	for(int k=l;k<=r;k++) if(used[k]) return false;
	return true;
}

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

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

		for(int k=l;k<=r;k++) used[k]=true;
		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++) used[z]=true;
			}
		}
	}

	for(auto [l,r]:cur) {
		for(int k=l;k<=r;k++) used[k]=false;
	}

	return cur.size();
}

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

	cin>>N;

	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});
	}

	M=f(-1);

	for(int i=0;i<N;i++) {
		if(f(i)+ans.size()==M) {
			auto [l,r]=v[i];
			for(int k=l;k<=r;k++) used[k]=true;
			ans.push_back(i);
		}
	}

	cout<<ans.size()<<'\n';
	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:79:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |   if(f(i)+ans.size()==M) {
      |      ~~~~~~~~~~~~~~~^~~

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