Submission #524910

#	Time	Username	Problem	Language	Result	Execution time	Memory
524910		amunduzbaev	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	172 ms	25564 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++;
	}
	
	//~ for(int i=0;i<n;i++) cout<<a[i][0]<<" "<<a[i][1]<<"\n";
	
	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]);
	} par[N - 1][0] = N;
	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=0;i<N;i++){
			if(par[i][j-1] < N) par[i][j] = par[par[i][j-1]][j-1];
			else par[i][j] = N;
		} 
	}
	auto get = [&](int l, int r){
		int res = 0;
		for(int j=19;~j;j--){
			if(par[l][j] <= r) l = par[l][j], res += (1 << j);
		} return res;
	};
	
	ss.insert({N - 1, N - 1});
	ss.insert({0, 0});
	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});
		assert(it != ss.begin());
		if((*--it)[1] > r[0]) continue;
		int lx = (*it)[1], rx = (*++it)[0];
		assert(it != ss.end());
		int lc = get(lx, r[0]), rc = get(r[1], rx);
		
		int tot = rc + lc + 1 + cc;
		if(rx < N) tot += tree.get(rx + 1, N);
		if(0 < lx) tot += tree.get(0, lx - 1);
		if(tot >= k){
			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";
	}
}

/*

11 3
34 69
62 76
9 25
4 37
32 35
34 53
6 57
7 19
4 14
12 39
48 48

*/

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