Submission #976263

#	Time	Username	Problem	Language	Result	Execution time	Memory
976263		happy_node	Event Hopping 2 (JOI21_event2)	C++17	1 / 100	70 ms	46292 KiB

event2

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

const int MX=1e5+5;
int N,K;
int L[MX], R[MX], nxt[MX], deg[MX];

vector<pair<int,int>> ptL[MX], ptR[MX];
map<int,int> id;
vector<int> adj[MX];

int up[MX][20];

void dfs(int v) {
	for(int k=1;k<20;k++) {
		up[v][k]=up[up[v][k-1]][k-1];
	}

	for(auto u:adj[v]) {
		up[u][0]=v;
		dfs(u);
	}
}

int calc(int l, int r) {
	int v=nxt[l], res=0;
	if(v==1e9) return 0;
	if(R[v]>r) return 0;

	for(int k=19;k>=0;k--) {
		if(up[v][k]!=0 && R[up[v][k]]<=r) {
			res+=1<<k;
			v=up[v][k];
		}
	}
	return res+1;
}

bool chk(pair<int,int> p, pair<int,int> q) {
	if(p.second<=q.first) return false;
	return true;
}

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

	cin>>N>>K;
	for(int i=1;i<=N;i++) {
		cin>>L[i]>>R[i];
		id[L[i]]=0;
		id[R[i]]=0;
	}
	int z=0;
	for(auto &[x,y]:id) {
		y=++z;
	}
	for(int i=1;i<=N;i++) {
		L[i]=id[L[i]];
		R[i]=id[R[i]];

		ptL[L[i]].push_back({R[i],i});
		ptR[R[i]].push_back({L[i],i});
	}

	pair<int,int> lst={1e9,1e9};

	for(int p=z;p>=1;p--) {
		for(auto [r,id]:ptL[p]) {
			lst=min(lst,make_pair(r,id));
		}
		nxt[p]=lst.second;
		for(auto [l,id]:ptR[p]) {
			if(lst.second!=1e9) {
				adj[lst.second].push_back(id);
			}
		}
	}

	for(int i=1;i<=N;i++) {
		for(auto j:adj[i]) deg[j]+=1;
	}
	
	for(int i=1;i<=N;i++) {
		if(!deg[i]) {
			dfs(i);
		}
	}

	set<pair<int,int>> ranges;

	ranges.insert({1,1});
	ranges.insert({z,z});

	vector<int> ans;

	for(int i=1;i<=N;i++) {
		auto it=ranges.lower_bound(make_pair(R[i],0));
		assert(it!=ranges.begin());
		it--;
		if(chk(*it,make_pair(L[i],R[i]))) continue; // intersected
		auto itt=ranges.lower_bound(make_pair(R[i],0));
		assert(itt!=ranges.end());

		int a=it->second,b=itt->first;
		if(1+calc(a,L[i])+calc(R[i],b)+calc(1,a)+calc(b,z)>=K) {
			assert(L[i]<=R[i]);
			ranges.insert({L[i],R[i]});
			ans.push_back(i);
		}
		if(ans.size()==K) break;
	}	

	if(ans.size()<K) {
		cout<<-1<<'\n';
		return 0;
	}

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

Compilation message (stderr)

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

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