Submission #417170

#	Time	Username	Problem	Language	Result	Execution time	Memory
417170		errorgorn	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	3093 ms	3240 KiB

event2

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

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k;
int l[100005],r[100005];
set<ii> s; 

// we need to check if the intercept of all ranges is null
// find the range exactly after the tile
// then check the range exactly before it?

bool in(ii i){
	auto it=s.ub(ii(i.se,-1));
	
	if (it==s.begin()) return false;
	
	return (*prev(it)).se>i.fi;
}

vector<ii> range; //to do greedy

int calc(){
	int curr=0;
	int ans=0;
	
	for (auto &it:range){
		if (curr<=it.fi && !in(it)){
			ans++;
			curr=it.se;
		}
	}
	
	return ans;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,0,n) cin>>l[x]>>r[x];
	rep(x,0,n) range.pub(ii(l[x],r[x]));
	
	sort(all(range),[](ii i,ii j){
		return i.se<j.se;
	});
	
	if (calc()<k){
		cout<<"-1"<<endl;
		return 0;
	}
	
	vector<int> ans;
	rep(x,0,n){
		if (!in(ii(l[x],r[x]))){
			s.insert(ii(l[x],r[x]));
			
			//for (auto &it:s) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
			//cout<<x<<" "<<calc()<<endl;
			
			if (calc()+sz(s)<k){
				s.erase(ii(l[x],r[x]));
			}
			else{
				ans.pub(x);
			}
		}
	}
	
	rep(x,0,k) cout<<ans[x]+1<<endl;
}

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