Submission #405589

#	Time	Username	Problem	Language	Result	Execution time	Memory
405589		dvdg6566	Event Hopping 2 (JOI21_event2)	C++14	32 / 100	3061 ms	19920 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first 
#define s second
#define mp make_pair
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound

const int MAXN = 200100;
const int MAXK = 19;
int L[MAXN][MAXK];
vpi V;
vi des;
int N,a,b,M,K;

int eval(int x,int y){
	int ans=0;
	// for(int k=MAXK-1;k>=0;--k)if(x<=y){
	// 	if(L[x][k]-1<=y){
	// 		x = L[x][k] + 1;
	// 		ans += (1<<k);
	// 	}
	// }
	while(x<=y&&L[x][0]-1<=y){ // fits within (x,y)
		x = L[x][0];
		++ans;
	}
	return ans;
}

set<pair<pi,int>> S;

int main(){
	cin>>N>>K;
	for(int i=0;i<N;++i){
		cin>>a>>b;
		--b;
		V.pb(a,b);
		des.pb(a);des.pb(b);
	}
	sort(ALL(des));des.resize(unique(ALL(des))-des.begin());
	for(auto &i:V){
		i.f = lb(ALL(des),i.f) - des.begin();
		i.s = lb(ALL(des),i.s) - des.begin();
	}
	vpi T;
	for(auto i:V)T.pb(i);
	sort(ALL(T));
	M=SZ(des)-1; // run from 0 to M-1	
	ll rc=1e9;
	for(int k=0;k<MAXK;++k)L[M+1][k]=1e9;

	for(int i=M;i>=0;--i){
		while(SZ(T)&&T.back().f>=i){
			rc=min(rc,T.back().s);
			T.pop_back();
		}
		L[i][0]=rc+1;
		for(int k=1;k<MAXK;++k){
			if(L[i][k-1] >= 1e9){
				L[i][k]=1e9;
				continue;
			}
			int t=L[i][k-1];
			L[i][k] = L[t][k-1];
		}
	}
	// cerr<<L[0][MAXK-1]<<'\n';
	assert(L[0][MAXK-1]>=1e9);
	int tot=eval(0,M);
	// cerr<<tot<<'\n';
	if(tot<K){
		cout<<-1<<'\n';
		return 0;
	}
	
	S.insert(mp(mp(-1,-1),-1));
	S.insert(mp(mp(0,M),tot));

	vi ans;
	for(int i=0;i<N;++i){
		a = V[i].f;
		b = V[i].s;
		auto x = --S.ub(mp(mp(a,1e9),-1e9));
		pi rng=x->f;
		int w=x->s;
		if(rng.f>a)assert(0);
		if(rng.s<b)continue;
		// rng.f, a, b, rng.s
		int c=eval(rng.f,a-1);
		int d=eval(b+1,rng.s);
		int nv=c+d;
		if(tot-w+1+nv<K)continue; // cannot take
		tot = tot-w+1+nv;
		ans.pb(i+1);
		S.erase(x);
		if(c)S.insert(mp(mp(rng.f,a-1),c));
		if(d)S.insert(mp(mp(b+1,rng.s),d));
		// cerr<<"Ins "<<i+1<<'\n';
	}
	while(SZ(ans)>K)ans.pop_back();
	for(auto i:ans)cout<<i<<'\n';
}

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