Submission #524898

#	Time	Username	Problem	Language	Result	Execution time	Memory
524898		amunduzbaev	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	118 ms	33348 KiB

event2

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

#define ar array

const int N = 2e5 + 5;
int par[N][20], pref[N][20];
set<ar<int, 2>> ss;

struct BIT{
	int tree[N + 5];
	void add(int i, int v){ ++i;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){ i++;
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	
	int get(int l, int r){
		return get(r) - get(--l);
	}
	
	void sett(int i, int v){
		add(i, v - get(i, i));
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k; cin>>n>>k;
	vector<ar<int, 2>> a(n);
	vector<int> p;
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1];
		p.push_back(i<<1);
		p.push_back(i<<1|1);
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return a[i>>1][i&1] < a[j>>1][j&1];
	});
	
	for(int i=0, last=1;i<2*n;){
		int j = i;
		while(j < 2*n && a[p[i]>>1][p[i]&1] == a[p[j]>>1][p[j]&1]){
			j++;
		} while(i < j){
			a[p[i]>>1][p[i]&1] = last;
			i++;
		} last++;
	}
	
	memset(par, 127, sizeof par);
	for(int i=0;i<n;i++){
		par[a[i][0]][0] = min(par[a[i][0]][0], a[i][1]);
		pref[a[i][1]][0] = max(pref[a[i][1]][0], a[i][0]);
	} par[N - 1][0] = N; pref[0][0] = -1;
	for(int i=1;i<N;i++) pref[i][0] = max(pref[i][0], pref[i-1][0]);
	for(int i=N-2;~i;i--) par[i][0] = min(par[i][0], par[i+1][0]);
	for(int j=1;j<20;j++){
		for(int i=1;i<N;i++){
			if(par[i][j-1] < N) par[i][j] = par[par[i][j-1]][j-1];
			else par[i][j] = N;
			if(~pref[i][j-1]) pref[i][j] = pref[pref[i][j-1]][j-1];
			else pref[i][j] = -1;
		} 
	}
	
	//~ for(int i=0;i<n;i++) cout<<a[i][0]<<" "<<a[i][1]<<"\n";
	//~ cout<<"\n";
	ss.insert({0, 0});
	ss.insert({N - 1, N - 1});
	vector<int> res;
	
	int cc = 0;
	for(int i=0;i<n && cc < k;i++){
		auto& r = a[i];
		auto it = ss.lower_bound({r[1], -1});
		if((*--it)[1] > r[0]) continue;
		int lx = (*it)[1], rx = (*++it)[0];
		int lef = r[0], rig = r[1];
		int rc = 0, lc = 0;
		for(int j=20;~j;j--){
			if(par[rig][j] <= rx) rig = par[rig][j], rc += (1 << j);
			if(pref[lef][j] >= lx) lef = pref[lef][j], lc += (1 << j);
		}
		
		int tot = rc + lc;
		if(rx < N) tot += tree.get(rx + 1, N);
		if(0 < lx) tot += tree.get(0, lx - 1);
		if(tot + 1 >= k - cc){
			ss.insert(r);
			tree.sett(lx, lc);
			tree.sett(r[1], rc);
			res.push_back(i);
			cc++;
		}
	}
	
	if(cc == k){
		for(auto x : res) cout<<x + 1<<"\n";
	} else {
		cout<<-1<<"\n";
	}
}

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