Submission #445123

#	Time	Username	Problem	Language	Result	Execution time	Memory
445123		mosiashvililuka	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	299 ms	31444 KiB

event2

#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int N=1000000002;
int a,b,c,d,e,i,j,ii,jj,zx,xc,k,sf[100009],mshrg[100009][19],pr[100009],mshlf[100009][19],lef,rig,mid,pas;
pair <int, int> p[100009];
pair <pair <int, int>, int> P[100009];
pair <pair <int, int>, pair <int, int> > PP;
set <pair <pair <int, int>, pair <int, int> > > s;
set <pair <pair <int, int>, pair <int, int> > >::iterator it,tt;
set <int> S;
set <int>::iterator IT;
int left(int q, int w){
	int sm=0;
	for(int h=17; h>=0; h--){
		if(mshlf[q][h]<=0||mshlf[q][h]>=a+1) continue;
		if(p[mshlf[q][h]].first<w) continue;
		sm+=(1<<h);
		q=mshlf[q][h];
	}
	return sm;
}
int right(int q, int w){
	int sm=0;
	for(int h=17; h>=0; h--){
		if(mshrg[q][h]<=0||mshrg[q][h]>=a+1) continue;
		if(p[mshrg[q][h]].second>w) continue;
		sm+=(1<<h);
		q=mshrg[q][h];
	}
	return sm;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>k;
	for(i=1; i<=a; i++){
		cin>>p[i].first>>p[i].second;
		P[i].first=p[i];P[i].second=i;
	}
	//cout<<endl<<endl<<endl;
	sort(P+1,P+a+1);
	sf[a]=a;
	for(i=a-1; i>=1; i--){
		if(P[i].first.second<=P[sf[i+1]].first.second){
			sf[i]=i;
		}else{
			sf[i]=sf[i+1];
		}
	}
	for(i=1; i<=a; i++){
		lef=0;rig=a+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			if(P[mid].first.first<p[i].second){
				lef=mid;
			}else{
				rig=mid;
			}
		}
		mshrg[i][0]=P[sf[lef+1]].second;
		//cout<<i<<" "<<mshrg[i][0]<<endl;
	}
	
	
	
	for(i=1; i<=a; i++){
		P[i].first.first=p[i].second;P[i].first.second=p[i].first;
		P[i].second=i;
	}
	sort(P+1,P+a+1);
	for(i=1; i<=a; i++) swap(P[i].first.first,P[i].first.second);
	pr[1]=1;
	for(i=2; i<=a; i++){
		if(P[i].first.first>=P[pr[i-1]].first.first){
			pr[i]=i;
		}else{
			pr[i]=pr[i-1];
		}
	}
	for(i=1; i<=a; i++){
		lef=0;rig=a+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			if(P[mid].first.second>p[i].first){
				rig=mid;
			}else{
				lef=mid;
			}
		}
		mshlf[i][0]=P[pr[rig-1]].second;
		//cout<<i<<" "<<mshlf[i][0]<<endl;
	}
	
	for(j=1; j<=17; j++){
		for(i=1; i<=a; i++){
			mshlf[i][j]=mshlf[mshlf[i][j-1]][j-1];
			mshrg[i][j]=mshrg[mshrg[i][j-1]][j-1];
		}
	}
	
	
	//cout<<right(3,100)<<endl;
	/*cout<<left(7,417144410)<<endl;
	return 0;*/
	//s.insert(make_pair(make_pair(0,0),make_pair()))
	pas=0;
	s.insert(mk(mk(0,0),mk(0,0)));
	s.insert(mk(mk(N,N),mk(0,0)));
	for(i=1; i<=a; i++){
		if(s.size()>=k+2) break;
		it=s.lower_bound(mk(mk(p[i].first,0),mk(0,0)));
		if((*it).first.first<p[i].second) continue;
		it--;
		if((*it).first.second>p[i].first) continue;
		it++;
		
		e=pas;
		//cout<<i<<" "<<pas<<endl;
		//cout<<(*it).first.first<<" "<<(*it).first.second<<" "<<(*it).second.first<<" "<<(*it).second.second<<endl;
		pas-=(*it).second.first;
		//cout<<i<<" "<<pas<<endl;
		it--;
		c=left(i,(*it).first.second);
		it++;
		pas+=c;
		d=right(i,(*it).first.first);
		pas+=d;
		pas++;
		//cout<<i<<" "<<pas<<endl;
		if(pas<k){
			pas=e;
			continue;
		}
		
		PP=(*it);
		s.erase(it);
		s.insert(mk(PP.first,mk(d,PP.second.second)));
		s.insert(mk(mk(p[i].first,p[i].second),mk(c,i)));
	}
	if(/*pas<k*/s.size()<k+2){
		cout<<-1;
		return 0;
	}
	for(it=s.begin(); it!=s.end(); it++){
		if((*it).second.second==0) continue;
		S.insert((*it).second.second);
	}
	
	for(IT=S.begin(); IT!=S.end(); IT++){
		cout<<(*IT)<<"\n";
		k--;
		if(k==0) break;
	}
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:112:14: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |   if(s.size()>=k+2) break;
      |      ~~~~~~~~^~~~~
event2.cpp:142:22: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |  if(/*pas<k*/s.size()<k+2){
      |              ~~~~~~~~^~~~

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