Submission #386299

#	Time	Username	Problem	Language	Result	Execution time	Memory
386299		kshitij_sodani	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	387 ms	42344 KiB

event2

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


int n,k;
int aa[200001];
int bb[200001];
int ma=0;
//int tree[4*200001];
vector<int> pre[400001];
int re[400001][9];
/*void build(int no,int l,int r){
	if(l==r){
		if(mi[l]==-1){
			tree[no]=2*n+1;
		}
		else{
			tree[no]=mi[no];
		}
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=min(tree[no*2+1],tree[no*2+2]);
	}
}*/
int mi;
int cal(int aa,int bb){
	int xx=mi;
	if(aa>0){
		xx=re[aa-1][0];
	}
	if(xx>bb){
		return 0;
	}
	int ans2=1;
	
	for(int j=17;j>=0;j--){
		int cot;
		if(j%2==0){
			cot=re[xx][j/2];
		}
		else{
			cot=re[re[xx][(j/2)]][(j/2)];
		}

		if(cot<=bb){
			//cout<<xx<<":"<<j<<":"<<cot<<endl;
			xx=cot;
			ans2+=(1<<j);
		}
	}
	return ans2;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	map<int,int> ss3;
	mi=2*n;
	for(int i=0;i<n;i++){
		cin>>aa[i]>>bb[i];
		aa[i]*=2;
		aa[i]+=1;
		bb[i]*=2;
		ss3[aa[i]]++;
		ss3[bb[i]]++;
	}

	int ind=-1;
	/*for(int i=0;i<2*n;i++){
		tree[i]=2*n;
	}*/
	
	map<int,int> tt;
	for(auto j:ss3){
		ind++;
		tt[j.a]=ind;
	}
	
	for(int i=0;i<n;i++){
		aa[i]=tt[aa[i]];
		ma=max(ma,aa[i]);
		bb[i]=tt[bb[i]];
		pre[aa[i]].pb(bb[i]);
	/*	if(mi[aa[i]]==-1){
			mi[aa[i]]=bb[i];
		}
		mi[aa[i]]=min(mi[aa[i]],bb[i]);*/
	}
	/*for(int i=0;i<n;i++){
		cout<<aa[i]<<":"<<bb[i]<<endl;
	}*/

	for(int i=2*n-1;i>=0;i--){
		re[i][0]=mi;
		for(auto j:pre[i]){
			mi=min(mi,j);
		}
	}
	for(int i=0;i<2*n;i++){
		pre[i].clear();
	}
	for(int i=0;i<9;i++){
		re[2*n][i]=2*n;
	}
	for(int j=1;j<9;j+=1){
		for(int i=0;i<2*n;i++){
			re[i][j]=re[i][j-1];
			for(int k=0;k<3;k++){
				re[i][j]=re[re[i][j]][j-1];
			}
		//	re[i][j]=re[re[i][j-1]][j-1];
		}
	}
/*	for(int i=0;i<n;i++){
		cout<<re[i][0]<<",";
	}
	cout<<endl;*/
	int cur=cal(0,2*n-1);
	//k=cur;
	//cout<<cur<<":"<<endl;
	if(cur<k){
		cout<<-1<<endl;
		return 0;
	}
	set<pair<int,int>> ss;
	ss.insert({0,2*n-1});
	vector<int> ans;

	for(int i=0;i<n;i++){
		if(ans.size()==k){
			break;
		}
		auto j=ss.upper_bound({aa[i],2*n});
		if(j==ss.begin()){
			continue;
		}
		j--;
		pair<int,int> no=*j;
		if((aa[i]>=no.a and bb[i]<=no.b)){
			//cout<<i<<"::"<<endl;
			int cot=cur-cal(no.a,no.b);
			if(no.a<aa[i]){
				cot+=cal(no.a,aa[i]-1);
			}
			if(no.b>bb[i]){
				cot+=cal(bb[i]+1,no.b);
			}
			cot+=1;

			if(cot>=k){
				cur=cot;
				ans.pb(i);
				ss.erase(no);
				if(no.a<aa[i]){
					ss.insert({no.a,aa[i]-1});
				}
				if(no.b>bb[i]){
					ss.insert({bb[i]+1,no.b});
				}
			}
		}
		else{
			continue;
		}
	}

//	cout<<ans.size()<<endl;
	for(auto j:ans){
		cout<<j+1<<endl;
	}








 
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:140:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |   if(ans.size()==k){
      |      ~~~~~~~~~~^~~

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