Submission #975548

#	Time	Username	Problem	Language	Result	Execution time	Memory
975548		happy_node	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	215 ms	41244 KiB

event2

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

const int MX=2e5+5, inf=1e9;

int N,K;
vector<pair<int,int>> vv;
vector<array<int,3>> v;
int dp[MX];
map<int,int> id;

set<pair<int,int>> st[MX];

struct segtree {
    	pair<int,int> t[4 * MX];
 
     	void update(int v, int l, int r, int pos, pair<int,int> val) {
           	if(l > pos || r < pos) return;
           	if(l == r) {
                 	t[v] = val;
                 	return;
           	}
           	int mid = (l + r) >> 1;
           	update(v * 2 + 0, l, mid + 0, pos, val);
           	update(v * 2 + 1, mid + 1, r, pos, val);
           	t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
     	}
 
     	pair<int,int>  query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return make_pair(1e9,1e9);
           	if(ql <= l && qr >= r) return t[v];
           	int mid = (l + r) >> 1;
           	return min(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      	}
} tt;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>K;

	for(int i=1;i<=N;i++) {
		int l,r;
		cin>>l>>r;
		v.push_back({r,l,i});
		vv.push_back({l,r});
		id[l]=0;
		id[r]=0;
	}

	int z=1;
	for(auto &[x,y]:id) y=z++;

	sort(v.begin(),v.end());
	for(auto [r,l,i]:v) {
		st[id[r]].insert({i,r});
	}

	for(int i=1;i<=2*N;i++) {
		if(st[i].size()) 
			tt.update(1,1,2*N,i,*st[i].begin());
		else
			tt.update(1,1,2*N,i,make_pair(inf,inf));
	}

	sort(vv.rbegin(),vv.rend());

	dp[0]=inf;
	for(auto [a,b]:vv) {
		int l=0,r=N,res=0;
		while(l<=r) {
			int mid=(l+r)/2;
			if(b<=dp[mid]) {
				res=mid,l=mid+1;
			} else {
				r=mid-1;
			}
		}
		dp[res+1]=max(dp[res+1],a);
	}

	if(!dp[K]) {
		cout<<-1<<'\n';
		return 0;
	}

	int cur=0, pt=0;

	set<array<int,3>> dels;
	for(auto [r,l,i]:v) {
		dels.insert({l,r,i});
	}

	id[1e9]=2*N;
	
	vector<int> ans;

	while(K>0) {
		// get min value lexicographically
		auto [V,R]=tt.query(1,1,2*N,id[cur],id[dp[K-1]]);

		ans.push_back(V);

		while(dels.size() && (*dels.begin())[0]<R) {
			auto [curL, curR, i]=*dels.begin();
			dels.erase(dels.begin());
			st[id[curR]].erase(make_pair(i,curR));

			tt.update(1,1,2*N,id[curR],(st[id[curR]].empty() 
				? make_pair(inf,inf) : *st[id[curR]].begin()));
			pt++;
		}
		cur=R;
		K--;
	}

	sort(ans.begin(),ans.end());

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

}

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