Submission #893869

#	Time	Username	Problem	Language	Result	Execution time	Memory
893869		iskhakkutbilim	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	224 ms	52260 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define ff first
#define ss second



int in(auto big, auto small){
	if(big.ff <= small.ff && big.ss >= small.ss) return 1;
	return 0;
}



auto split(auto big, auto small){
	vector<pair<int, int> > v;
	v.push_back({big.ff, small.ff});
	v.push_back({small.ss, big.ss});
	return v;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k; cin >> n >> k;
	vector<pair<int, int> > a(n);
	for(int i = 0;i < n; i++){
		cin >> a[i].ff >> a[i].ss;
	}
	vector<int> X;
	for(int i = 0;i < n; i++){
		X.push_back(a[i].ff);
		X.push_back(a[i].ss);
	}
	sort(all(X));
	X.erase(unique(all(X)), X.end());
	auto get = [&](int cor){
		return lower_bound(all(X), cor) - X.begin() + 1;
	};
	int sz = n * 2;
	vector< vector<int> > up(sz+2, vector<int>(20, sz+1));
	for(int i = 0;i < n; i++){
		a[i].ff = get(a[i].ff);
		a[i].ss = get(a[i].ss);
		up[a[i].ff][0] = min(up[a[i].ff][0], a[i].ss); 
	}
	int mn = sz+1;
	for(int i = sz; i >= 1; i--){
		mn = min(mn, up[i][0]);
		up[i][0] = mn;
	}
	for(int j = 1;j < 20; j++){
		for(int i = 1;i <= sz; i++){
			up[i][j] = up[up[i][j-1]][j-1];
		}
	}
	auto check=[&](int l, int r){
		int len = 0;
		for(int i = 19; i >= 0; i--){
			if(up[l][i] <= r){
				l = up[l][i];
				len+= (1<<i);
			}
		}
		return len;
	};
	
	int cnt = check(1, sz);
	if(cnt < k){
		cout << "-1";
		return 0;
	}
	
	vector<int> ans;
	set<pair<int, int> > range;
	range.insert({1, sz});
	for(int i = 0;i < n && (int)ans.size() < k; i++){
		auto it = range.upper_bound(make_pair(a[i].ff, INT_MAX));
		if(it == range.begin()) continue;
		it--;
		if(!in(*it, a[i])) continue;
		int cn = check(it->ff, it->ss);
		auto spt = split(*it, a[i]);
		int cn1 = check(spt[0].ff, spt[0].ss);
		int cn2 = check(spt[1].ff, spt[1].ss);
		
		if(cnt - cn + cn1 + cn2 + 1 < k){
			continue;
		}
		cnt = cnt - cn + cn1 + cn2 + 1;
		ans.push_back(i+1);
		range.erase(it);
		range.insert(spt[0]);
		range.insert(spt[1]);
	}

	for(auto x : ans) cout << x << '\n';
	
	
	
	
	
	
	
	return 0;
}

Compilation message (stderr)

event2.cpp:10:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   10 | int in(auto big, auto small){
      |        ^~~~
event2.cpp:10:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   10 | int in(auto big, auto small){
      |                  ^~~~
event2.cpp:17:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto split(auto big, auto small){
      |            ^~~~
event2.cpp:17:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto split(auto big, auto small){
      |                      ^~~~

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