Submission #722556

#	Time	Username	Problem	Language	Result	Execution time	Memory
722556		minhcool	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	584 ms	67996 KiB

event2

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, k;
int l[N], r[N];

iii seg[N];

int mini[N];
int nxt[N];
int eval[N][21];

bool cook[N];

int le[N], ri[N];
set<ii> seg1[N], seg2[N];
int comp[N];
//int mn_r[N];

int cal(int le, int ri){
	int temp = lower_bound(seg + 1, seg + n + 1, make_pair(make_pair(le, -oo), -oo)) - seg;
	if(temp == (n + 1)) return 0;
	temp = mini[temp];
	//cout << temp << "\n";
	if(r[temp] > ri) return 0;
	int answer = 1;
	for(int i = 18; i >= 0; i--){
		//cout << eval[temp][i] << "\n";
		if(eval[temp][i] == oo) continue;
		if(r[eval[temp][i]] <= ri){
			answer += (1LL << i);
			temp = eval[temp][i];
		}
	}
	return answer;
}

void process(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> seg[i].fi.fi >> seg[i].fi.se;
		seg[i].se = i;
		l[i] = seg[i].fi.fi, r[i] = seg[i].fi.se;
	}
	sort(seg + 1, seg + n + 1);
	mini[n + 1] = oo;	
	for(int i = n; i >= 1; i--){
		mini[i] = mini[i + 1];
		if(i == n || seg[i].fi.se <= r[mini[i]]) mini[i] = seg[i].se;
		int temp = lower_bound(seg + 1, seg + n + 1, make_pair(make_pair(seg[i].fi.se, -oo), -oo)) - seg;
		if(temp == (n + 1)) nxt[seg[i].se] = oo;
		else nxt[seg[i].se] = mini[temp];
		if(nxt[seg[i].se] == seg[i].se) nxt[seg[i].se] = oo;
		//cout << i << " " << temp << " " << nxt[seg[i].se] << "\n";
		//cout << seg[i].se << " " << temp << " " << nxt[seg[i].se] << "\n";
		eval[seg[i].se][0] = nxt[seg[i].se];
	}
	for(int i = 1; i <= 18; i++){
		for(int j = 1; j <= n; j++){
			if(eval[j][i - 1] == oo) eval[j][i] = oo;
			else eval[j][i] = eval[eval[j][i - 1]][i - 1];
		}
	}
	le[1] = 0, ri[1] = 1e9;
	for(int i = 1; i <= n; i++){
		seg1[1].insert({l[i], i});
		seg2[1].insert({r[i], i});
		comp[i] = 1;
	}
	int cur = cal(0, 1e9);
	//cout << cur << "\n";
	//exit(0);
	if(cur < k){
		cout << -1;
		return;
	}
	cur -= k;
	int tol_comp = 1;
	int num = 0;
	for(int i = 1; i <= n; i++){
		if(cook[i]) continue;
		cook[i] = 1;
		//if(l[i] < le[root] || r[i] > ri[root]) continue;
		int root = comp[i];
		int diff = cal(le[root], ri[root]);
		diff -= cal(le[root], l[i]) + cal(r[i], ri[root]) + 1;
		//cout << diff << "\n";
		assert(diff >= 0);
		if(cur < diff){
			seg1[comp[i]].erase({l[i], i});
			seg2[comp[i]].erase({r[i], i});
		//	cook[i] = 1;
			continue;
		}
		num++;
		cur -= diff;
		bool which = 0;
		set<ii>::iterator it1 = seg1[root].lower_bound({r[i], -oo}), it2 = seg2[root].lower_bound({l[i] + 1, -oo});
		if(it2 == seg2[root].begin()) which = 0;
		else{
			it2--;
			while(1){
				if(it1 == seg1[root].end()){
					which = 1;
					break;
				}
				if(it2 == seg2[root].begin()){
					which = 0;
					break;
				}
				it1++;
				it2--;
			}
		}
		if(!which){
			tol_comp++;
			le[tol_comp] = le[root], ri[tol_comp] = l[i];
			le[root] = r[i];
			set<ii>::iterator it1 = seg1[root].lower_bound({r[i], -oo}), it2 = seg2[root].lower_bound({l[i] + 1, -oo});
			vector<int> er;
			if(it2 != seg2[root].begin()){
				it2--;
				for(;; it2--){
					er.pb((*it2).se);
					if(it2 == seg2[root].begin()) break;
				}
			}
			for(auto it : er){
				comp[it] = tol_comp;
				seg1[root].erase({l[it], it});
				seg2[root].erase({r[it], it});
				seg1[tol_comp].insert({l[it], it});
				seg2[tol_comp].insert({r[it], it});
			}
			er.clear();
			it1 = seg1[root].begin();
			for(; it1 != seg1[root].end(); it1++){
				if((*it1).fi >= r[i]) break;
				er.pb((*it1).se);
			}
			for(auto it : er){
				cook[it] = 1;
				seg1[root].erase({l[it], it});
				seg2[root].erase({r[it], it});
			}
		}
		else{
			tol_comp++;
			le[tol_comp] = r[i], ri[tol_comp] = ri[root];
			ri[root] = l[i];
			set<ii>::iterator it1 = seg1[root].lower_bound({r[i], -oo});
			vector<int> er;
			for(; it1 != seg1[root].end(); it1++){
				er.pb((*it1).se);
				//if(it1 == seg2[root].begin()) break;
			}
			for(auto it : er){
				comp[it] = tol_comp;
				seg1[root].erase({l[it], it});
				seg2[root].erase({r[it], it});
				seg1[tol_comp].insert({l[it], it});
				seg2[tol_comp].insert({r[it], it});
			}
			er.clear();
			if(seg2[root].size()){
				it1 = seg2[root].end();
				it1--;
				for(; ; it1--){
					if((*it1).fi <= l[i]) break;
					er.pb((*it1).se);
					if(it1 == seg2[root].begin()) break;
				}
				for(auto it : er){
					cook[it] = 1;
					seg1[root].erase({l[it], it});
					seg2[root].erase({r[it], it});
				}
			}
		}
		cout << i << "\n";
		if(num == k) break;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("event.inp", "r", stdin);
	//freopen("event.out", "w", stdout);
	cin.tie(0);
	process();
}

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