Submission #885562

#	Time	Username	Problem	Language	Result	Execution time	Memory
885562		willychan	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	3081 ms	3352 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
struct seg{
	int l;
	int r;
	int ind;
};

vector<seg> arr; 
vector<bool> taken;
vector<int> frontans;
vector<int> backans;
vector<int> frontord;
vector<int> backord;
int n;
void rebuilt(){
	for(int i=0;i<n;i++){
		frontans[i]=0;
		backans[i]=0;
	}
	int prev = -1;
	for(int i=0;i<n;i++){
		if(arr[frontord[i]].l<prev || taken[frontord[i]]){
			if(i) frontans[i] = frontans[i-1];
			else frontans[i]=0;
		}else{
			if(i) frontans[i] = frontans[i-1]+1;
			else frontans[i]=1;
			prev = arr[frontord[i]].r;
		}
	}
	prev = 1e9;
	for(int i=0;i<n;i++){
		if(arr[backord[i]].r>prev || taken[backord[i]])	{
			if(i) backans[i] = backans[i-1];
			else backans[i]=0;
		}else{
			if(i) backans[i] = backans[i-1]+1;
			else backans[i]=1;
			prev = arr[backord[i]].l;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int K;cin>>n>>K;
	arr.resize(n+1);
	taken.resize(n+1);
	frontans.resize(n+1);
	backans.resize(n+1);
	for(int i=1;i<=n;i++){
		int a,b;cin>>a>>b;
		arr[i].l = a;
		arr[i].r = b;
		arr[i].ind = i;
	}
	for(int i=1;i<=n;i++) frontord.push_back(i);
	for(int i=1;i<=n;i++) backord.push_back(i);
	sort(frontord.begin(),frontord.end(),[&](const int &a,const int &b){return arr[a].r<arr[b].r;});
	sort(backord.begin(),backord.end(),[&](const int &a,const int &b){return arr[a].l>arr[b].l;});
	rebuilt();
	for(int i=1;i<=n;i++){
		if(taken[i]) continue;
		/*
		cout<<i<<":"<<"\n";
		for(int i=0;i<n;i++){
			cout<<frontans[i]<<" "; 
		}
			cout<<"\n";
		for(int i=0;i<n;i++){
			cout<<backans[i]<<" "; 
		}
			cout<<"\n";
		//if(taken[i]) continue;
		*/
			
		if(K==0) return 0;
		int total = 1;		
		int l = -1;int r = n;
		while(r-l>1){
			int mid = (l+r)/2;
			if(arr[frontord[mid]].r<=arr[i].l) l = mid;
			else r = mid;
		}
		total+=(l<0)?(0):frontans[l];
		l = -1;r = n;
		while(r-l>1){
			int mid = (l+r)/2;
			if(arr[backord[mid]].l>=arr[i].r) l = mid;
			else r = mid;
		}
		total+=(l<0)?(0):backans[l];
		if(total>=K){
			cout<<i<<"\n";
			K--;
			for(int p=1;p<=n;p++){
				if(max(arr[p].l,arr[i].l)<min(arr[p].r,arr[i].r)) taken[p]=1;
			}
		}else{
			taken[i]=1;
		}
		rebuilt();
	}
	if(K) cout<<-1<<"\n";
	return 0;
}

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