Submission #1253582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253582		WH8	Event Hopping 2 (JOI21_event2)	C++20	0 / 100	73 ms	24624 KiB

event2

#include <bits/stdc++.h>

using namespace std;
#define f first
#define s second
#define pb push_back
#define ld long double
#define pll pair<int, int>
#define iii tuple<int,int,int>
#define int long long 
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)

struct seg{
	int l, r, ind;
	seg(int L, int R, int IND): l(L), r(R), ind(IND) {}
	bool operator<(seg const &o) const {
        if (r != o.r) return r < o.r;
        return ind < o.ind;
    }
};

int n,k, cur;
vector<seg> v, sv;
vector<vector<int>> p(100005, vector<int>(20, -1));
set<seg> st;
vector<int> ans;

int mxr(int sind, int r){
	int cur=sind, ret=0;
	//~ printf("sind %lld r %lld\n", sind, r);
	if(v[sind].r > r)return 0;
	for(int k=19;k>=0;k--){
		//~ printf("2^%lld th parent of %lld is %lld\n", k, cur, p[cur][k]);
		if(p[cur][k]==-1 or v[p[cur][k]].r > r)continue;
		ret+=(1<<k);
		cur=p[cur][k];
	}
	return ret;
}

signed main(){
	cin>>n>>k;
	v.push_back(seg(0,0,0));
	sv.push_back(seg(0,0,0));
	for(int i=1;i<=n;i++){
		int l,r;cin>>l>>r;
		v.push_back(seg(l, r, i));
		sv.push_back(seg(l, r, i));
	}
	sort(sv.begin(),sv.end(),[&](auto a,auto b){
		return a.r<b.r;
	});
	stack<seg> s;
	for(int i=0;i<=n;i++){
		while(!s.empty() and s.top().r <= sv[i].l){
			p[s.top().ind][0]=sv[i].ind;
			s.pop();
		}
		s.push(sv[i]);
	}
	//~ for(int i=0;i<=n;i++){
		//~ cout<<i<<": "<<p[i][0]<<endl;
	//~ }
	//~ return 0;
	for(int k=1;k<20;k++){
		for(int i=0;i<=n;i++){
			if(p[i][k-1] != -1)p[i][k]=p[p[i][k-1]][k-1];
		}
	}
	cur=mxr(0, 1e9+5);
	//~ cout<<mxr(1, 1e9+5);
	//~ return 0;
	if(cur < k){
		cout<<-1;
		return 0;
	}
	st.insert(v[0]);
	for(int i=1;i<=n;i++){
		seg key(0, v[i].l, -1);
		auto it=st.lower_bound(key);
		auto prv=prev(it);
		int sind=0, r=1e9+5;
		if (it!=st.end()){
			r=(*it).l;
			if(r < v[i].r)continue;
		}
		sind=(*prv).ind;
		if(v[sind].r > v[i].l) continue;
		
		int rem=mxr(sind, r);
		int nwa=mxr(sind, v[i].l), nwb=mxr(v[i].ind, r);
		//~ printf("v[i].ind %lld, r %lld\n", v[i].ind, r);
		int cand=nwa+nwb+1;
		
		if(cur - rem + cand >= k){
			cur=cur-rem+cand;
			st.insert(v[i]);
			ans.pb(i);
		}	
		//~ printf("i %lld, sind %lld, r %lld, rem %lld, nwa %lld, nwb %lld\n", i, sind, r, rem, nwa, nwb);
	}
	assert(ans.size() >=k);
	for(int i=0;i<k;i++){
		cout<<ans[i]<<"\n";
	}
		
}
/*
5 4
1 10
1 3
3 4
4 5
5 6

*/

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