Submission #947034

#	Time	Username	Problem	Language	Result	Execution time	Memory
947034		vjudge1	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	3051 ms	22668 KiB

event2

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
vector<long long>res;
long long n,k;
pair<long long,long long>all[maxn];
vector<long long>alll[maxn],allr[maxn];

void vorod(){
	cin>>n>>k;
	vector<long long>allind;
	for(long long i=1;i<=n;i++){
		cin>>all[i].first>>all[i].second;
		all[i].second--;
		allind.push_back(all[i].first);
		allind.push_back(all[i].second);
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(long long i=1;i<=n;i++){
		all[i].first=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
		all[i].second=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin();
		alll[all[i].first].push_back(i);
		allr[all[i].second].push_back(i);
	}
}
vector<pair<long long,long long>>allv;
set<pair<int,int>>inds;
void pre(){
	set<pair<long long,long long>>st;
	for(long long i=0;i<maxn;i++){
		long long mn=maxn+2;
		for(auto x:alll[i]){
			mn=min(mn,all[x].second);
		}
		while((long long)st.size()>0&&(*st.rbegin()).first>=mn){
			st.erase(*st.rbegin());
		}
		for(auto x:alll[i]){
			if(all[x].second==mn){
				st.insert(make_pair(all[x].second,x));
				mn=-1;
			}
		}
		for(auto x:allr[i]){
			if(st.count(make_pair(i,x))==1){
				st.erase(make_pair(i,x));
				allv.push_back(make_pair(all[x].first,all[x].second));
			}
		}
	}
}

bool eshy(long long l,long long r,long long ll,long long rr){
	if(l>ll){
		swap(l,ll);
		swap(r,rr);
	}
	return ll<=r;
}

bool esh(long long a,long long b){
	return eshy(all[a].first,all[a].second,all[b].first,all[b].second);
}

long long cal(){
	long long ret=0,r=-1;
	for(auto x:allv){
		long long f=1;
		auto z=inds.lower_bound(make_pair(x.first,x.first));
		if((int)inds.size()>0&&(*inds.rbegin()).first>=x.first){
			if(eshy(x.first,x.second,(*z).first,(*z).second)){
				f=0;
			}
		}
		if((int)inds.size()>0&&(*inds.begin()).first<x.first){
			z--;
			if(eshy(x.first,x.second,(*z).first,(*z).second)){
				f=0;
			}
		}
		if(x.first<=r||f==0){
			continue;
		}
		ret++;
		r=x.second;
	}
	return ret;
}

void can(long long i){
	auto x=all[i];
	auto z=inds.lower_bound(make_pair(x.first,x.first));
	if((int)inds.size()>0&&(*inds.rbegin()).first>=x.first){
		if(eshy(x.first,x.second,(*z).first,(*z).second)){
			return ;
		}
	}
	if((int)inds.size()>0&&(*inds.begin()).first<x.first){
		z--;
		if(eshy(x.first,x.second,(*z).first,(*z).second)){
			return ;
		}
	}
	inds.insert(make_pair(all[i].first,all[i].second));
	res.push_back(i);
	if(cal()+(long long)res.size()<k){
		res.pop_back();
		inds.erase(make_pair(all[i].first,all[i].second));
	}
}

void solve(){
	for(long long i=1;i<=n;i++){
		if((long long)res.size()==k){
			break;
		}
		can(i);
	}
}

void khor(){
	if((long long)res.size()<k){
		cout<<-1<<"\n";
		return ;
	}
	for(auto x:res){
		cout<<x<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

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