Submission #523095

#	Time	Username	Problem	Language	Result	Execution time	Memory
523095		nathanlee726	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	277 ms	56164 KiB

event2

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

int n,k,dp[200010][18],balbit[200010],ss=0,ind=0,s[200010];
bool ud[200010];
pii pt[100010],pt1[100010],bd[200010];
map<int,int> mm;
vector<int> tv;

void ADD(int x,int vl){
	for(;x<=200006;x+=(x&(-x)))balbit[x]+=vl;
}

int QRY(int x){
	int re=0;
	for(;x>0;x-=(x&(-x)))re+=balbit[x];
	return re;
}

bool cmp(pii a,pii b){
	return a.Y<b.Y;
}

void check(){
	F(n)pt1[i]=pt[i];
	sort(pt1,pt1+n,cmp);
	int cnt=0,p=-1;
	F(n)if(pt1[i].X>=p)cnt++,p=pt1[i].Y;
	if(cnt<k){
		cout<<"-1"<<endl;
		exit(0);
	}
	ss=cnt;
	return;
}

int getv(int l,int r){
	int re=0;
	for(int i=17;i>=0;i--){
		if(dp[l][i]!=-1&&dp[l][i]<=r)l=dp[l][i],re+=(1ll<<i);
	}
	return re;
}

signed main(){
	IOS();
	cin>>n>>k;
	F(n)cin>>pt[i].X>>pt[i].Y,tv.pb(pt[i].X),tv.pb(pt[i].Y);
	sort(all(tv));
	tv.erase(unique(all(tv)),tv.end());
	memset(dp,-1,sizeof(dp));
	F(sz(tv))mm[tv[i]]=i+1;
	F(n)pt[i].X=mm[pt[i].X],pt[i].Y=mm[pt[i].Y];
	F(n)dp[pt[i].X][0]=(dp[pt[i].X][0]==-1?pt[i].Y:min(pt[i].Y,dp[pt[i].X][0]));
	int mn=-1;
	for(int i=200005;i>=1;i--){
		if(mn!=-1)dp[i][0]=(dp[i][0]==-1?mn:min(mn,dp[i][0]));
		if(dp[i][0]!=-1)mn=(mn==-1?dp[i][0]:min(mn,dp[i][0]));
	}
	Fi(j,17)for(int i=1;i<=200005;i++)dp[i][j+1]=(dp[i][j]==-1?-1:dp[dp[i][j]][j]);
	memres(balbit);
	check();
	memres(ud);
	memres(s);
	s[0]=ss;
	bd[0]={1,200005};
	vector<int> o;
	F(n){
		int id=QRY(pt[i].X),id1=QRY(pt[i].Y);
		if(ud[id]||id!=id1)continue;
		int ts=ss-s[id]+1;
		assert(bd[id].X<=pt[i].X&&pt[i].Y<=bd[id].Y);
		int v1=getv(bd[id].X,pt[i].X);
		int v2=getv(pt[i].Y,bd[id].Y);
		ts+=(v1+v2);
		if(ts>=k){
			ud[id]=1;
			ind++;
			bd[ind]={bd[id].X,pt[i].X};
			ADD(bd[id].X,ind-id);
			ADD(pt[i].X+1,id-ind);
			s[ind]=v1;
			ind++;
			bd[ind]={pt[i].Y,bd[id].Y};
			ADD(pt[i].Y,ind-id);
			ADD(bd[id].Y+1,id-ind);
			s[ind]=v2;
			ss=ts;
			o.pb(i+1);
			if(sz(o)==k)break;
		}
	}
	for(int i:o)cout<<i<<endl;
	return 0;
}

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