Submission #393031

#	Time	Username	Problem	Language	Result	Execution time	Memory
393031		oolimry	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	200 ms	18468 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

const lint inf = 0x3f3f3f3f;
struct range{ int l, r, id; };
vector<range> ranges;

int p[19][100005];
int order[100005];

set<ii> taken;

lint solve(lint s, lint limit){
	if(ranges[s].r > limit) return 0;
	lint res = 0;
	for(int k = 18;k >= 0;k--){
		int ns = p[k][s];
		if(ranges[ns].r <= limit){
			res += (1<<k);
			s = ns;
		}
	}
	return res+1;
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, K; cin >> n >> K;
	for(int i = 1;i <= n;i++){
		int l, r; cin >> l >> r;
		ranges.push_back({l,r,i});
	}
	
	ranges.push_back({inf+10, inf+10, n});
	sort(all(ranges), [&](range a, range b){ return a.r < b.r; });
	for(int i = 0;i <= 18;i++) fill(p[i], p[i]+n+5, n);
	
	set<ii> S;
	
	for(int i = 0;i < n;i++){
		range R = ranges[i];
		while(!S.empty()){
			auto it = S.begin();
			if(it->first <= R.l){
				p[0][it->second] = i;
				S.erase(it);
			}
			else break;
		}
		S.insert({R.r,i});
		order[R.id] = i;
	}
	
	for(int k = 1;k <= 18;k++){
		for(int i = 0;i < n;i++) p[k][i] = p[k-1][p[k-1][i]];
	}
	
	vector<int> ans;
	int cnt = solve(0, inf-2);
	
	if(cnt < K){
		cout << -1; return 0;
	}
	
	taken.insert({inf,inf});
	
	for(int x = 1;x <= n;x++){
		int i = order[x];
		range R = ranges[i];
		
		auto nxt = taken.lower_bound({R.r, -1});
		int s = 0;
		if(nxt != taken.begin()){
			auto pre = prev(nxt);
			int pid = pre->second;
			if(ranges[pid].r > R.l) continue;
			
			s = p[0][pid];
		}
		else s = 0;

		int newcnt = cnt;
		newcnt += solve(s, R.l);
		newcnt += solve(i, nxt->first);
		newcnt -= solve(s, nxt->first);
		
		if(newcnt >= K){
			ans.push_back(R.id);
			taken.insert({R.l, i});
			cnt = newcnt;
		}
	}
	
	for(int i = 0;i < K;i++) cout << ans[i] << "\n";
}

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