Submission #1210603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210603		emptypringlescan	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	153 ms	16676 KiB

event2

#include <bits/stdc++.h>
using namespace std;
pair<int,int> arr[100005],srt[100005];
vector<pair<pair<int,int>,int> > mono;
int n,k;
int nxt[20][100005];
int nombor(int l, int r){
	int ind=lower_bound(mono.begin(),mono.end(),make_pair(make_pair(l,-1),-1))-mono.begin();
	if(ind==(int)mono.size()) return 0;
	int cur=mono[ind].second;
	if(srt[cur].second>r) return 0;
	int ret=1;
	for(int i=19; i>=0; i--){
		if(nxt[i][cur]==-1||srt[nxt[i][cur]].second>r) continue;
		ret+=(1<<i);
		cur=nxt[i][cur];
	}
	return ret;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; i++){
		cin >> arr[i].first >> arr[i].second;
		srt[i]=arr[i];
	}
	sort(srt,srt+n);
	for(int i=0; i<n; i++){
		if(i&&srt[i].first==srt[i-1].first) continue;
		while(!mono.empty()&&mono.back().first.second>=srt[i].second) mono.pop_back();
		mono.push_back({srt[i],i});
	}
	memset(nxt,-1,sizeof(nxt));
	for(int i=0; i<n; i++){
		int ind=lower_bound(mono.begin(),mono.end(),make_pair(make_pair(srt[i].second,-1),-1))-mono.begin();
		if(ind==(int)mono.size()) nxt[0][i]=-1;
		else nxt[0][i]=mono[ind].second;
	}
	for(int i=1; i<20; i++){
		for(int j=0; j<n; j++){
			if(nxt[i-1][j]==-1) continue;
			nxt[i][j]=nxt[i-1][nxt[i-1][j]];
		}
	}
	set<pair<int,int> > ran;
	set<pair<int,int> >::iterator it;
	ran.insert({0,1'000'000'005});
	vector<int> ans;
	int can=nombor(0,1'000'000'005);
	for(int i=0; i<n; i++){
		it=ran.upper_bound(make_pair(arr[i].first+1,-1));
		if(it==ran.begin()) continue;
		it--;
		pair<int,int> big=*it;
		if(big.first>arr[i].first||big.second<arr[i].second) continue;
		int net=nombor(big.first,arr[i].first)+nombor(arr[i].second,big.second)+1-nombor(big.first,big.second);
		//cout << i << ' ' << nombor(big.first,arr[i].first) << ' ' << nombor(arr[i].second,big.second)  << '\n';
		if(can+net>=k){
			//cout << "take\n";
			can+=net;
			ran.erase(big);
			ran.insert({big.first,arr[i].first});
			ran.insert({arr[i].second,big.second});
			ans.push_back(i+1);
		}
	}
	if((int)ans.size()<k) cout << -1;
	else for(int i=0; i<k; i++) cout << ans[i] << '\n';
}

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