Submission #241066

#	Time	Username	Problem	Language	Result	Execution time	Memory
241066		kshitij_sodani	Port Facility (JOI17_port_facility)	C++17	0 / 100	61 ms	94328 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n;
llo mod=1e9+7;
pair<llo,llo> it[1000001];
llo vis[1000001];
//vector<llo> adj[1000001];

llo st=0;
vector<pair<llo,llo>> tree[4000001];
llo tree2[4000001];
llo tree3[4000001];
vector<pair<llo,llo>> ac;
void build(llo no,llo l,llo r){
	if(l==r){
		tree[no].pb({ac[l].b,l});
	}
	else{
		llo mid=(l+r)/2;
		llo ind=0;
		llo ind2=0;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
			if(tree[no*2+1][ind].a<tree[no*2+2][ind].a){
				tree[no].pb(tree[no*2+1][ind]);
				ind+=1;
			}
			else{
				tree[no].pb(tree[no*2+2][ind2]);
				ind2+=1;
			}
		}
		while(ind<tree[no*2+1].size()){
			tree[no].pb(tree[no*2+1][ind]);
			ind+=1;
		}
		while(ind2<tree[no*2+2].size()){
			tree[no].pb(tree[no*2+2][ind2]);
			ind2+=1;
		}
	}
}
void update(llo no,llo l,llo r,llo i,llo col){
	if(l==r){
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,col);
		}
		else{
			update(no*2+2,mid+1,r,i,col);
		}
	}
	if(col==1){
		tree2[no]=max(tree2[no],ac[i].b);
	}
	else{
		tree3[no]=max(tree3[no],ac[i].b);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb,llo val,llo col){
	if(r<aa or l>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		while(tree[no].size()){
			if(vis[tree[no].back().b]){
				tree[no].pop_back();
				continue;
			}
			break;
		}
		if(col==1){
			if(tree2[no]>val){
				st=1;
			}
		}
		if(col==2){
			if(tree3[no]>val){
				st=1;
			}
		}
		if(tree[no].size()==0){
			return -1;
		}
		if(tree[no].back().a<=val){
			return -1;
		}
		return tree[no].back().b;
	}
	else{
		llo mid=(l+r)/2;
		llo x=query(no*2+1,l,mid,aa,bb,val,col);
		if(x!=-1){
			return x;
		}
		return query(no*2+2,mid+1,r,aa,bb,val,col);
	}
}

void dfs(llo no,llo col=1){
	vis[no]=col;
	update(0,0,n-1,no,col);
	llo low=no;
	llo high=n-1;
	while(low<high-1){
		llo mid=(low+high)/2;
		if(ac[mid].a<=ac[no].b){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	llo ind=low;
	if(ac[high].a<=ac[no].b){
		ind=max(ind,high);
	}
	while(true){
		llo x=query(0,0,n-1,no,ind,ac[no].b,col);//add details
		if(x==-1){
			break;
		}
		dfs(x,3-col);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i].a>>it[i].b;
		ac.pb({it[i].a,it[i].b});
	}
	sort(ac.begin(),ac.end());
	/*for(llo i=0;i<n;i++){
		ind[ac[i].b]=i;
	}*/


/*	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			if(j==i){
				continue;
			}
			if(it[i].a<=it[j].a and it[i].b<=it[j].b and it[i].b>=it[j].a){
				adj[i].pb(j);
				adj[j].pb(i);
		//		cout<<i<<","<<j<<endl;
			}
		}
	}*/
	build(0,0,n-1);
	llo co=0;
	for(llo i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
			co+=1;
		}
	}
	if(st){
		cout<<0<<endl;
	}
	else{
		llo ans=1;
		for(llo i=0;i<co;i++){
			ans*=2;
			ans%=mod;
		}
		cout<<ans<<endl;

	}








	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void build(llo, llo, llo)':
port_facility.cpp:30:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp:30:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size() and ind2<tree[no*2+2].size()){
                                     ~~~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp:40:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp:44:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<tree[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22