Submission #241092

#	Time	Username	Problem	Language	Result	Execution time	Memory
241092		kshitij_sodani	Port Facility (JOI17_port_facility)	C++17	100 / 100	5715 ms	759352 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'
int n;
int mod=1e9+7;
pair<int,int> it[1000001];
int vis[1000001];
//vector<int> adj[1000001];

int st=0;
vector<pair<int,int>> tree[4000001];
vector<pair<int,int>> tree4[4000001];

int tree2[4000001];
int tree3[4000001];
int tree5[4000001];
int tree6[4000001];
int ind[1000001];

vector<pair<int,int>> ac;
vector<pair<pair<int,int>,int>> cc;

void build(int no,int l,int r){
	if(l==r){
		tree[no].pb({ac[l].b,l});
	}
	else{
		int mid=(l+r)/2;
		int ind=0;
		int 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][ind2].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 build2(int no,int l,int r){
	tree5[no]=3*n;
	tree6[no]=3*n;
	if(l==r){
		tree4[no].pb({cc[l].a.b,cc[l].b});
	}
	else{
		int mid=(l+r)/2;
		int ind=0;
		int ind2=0;
		build2(no*2+1,l,mid);
		build2(no*2+2,mid+1,r);
		while(ind<tree4[no*2+1].size() and ind2<tree4[no*2+2].size()){
			if(tree4[no*2+1][ind].a>tree4[no*2+2][ind2].a){
				tree4[no].pb(tree4[no*2+1][ind]);
				ind+=1;
			}
			else{
				tree4[no].pb(tree4[no*2+2][ind2]);
				ind2+=1;
			}
		}
		while(ind<tree4[no*2+1].size()){
			tree4[no].pb(tree4[no*2+1][ind]);
			ind+=1;
		}
		while(ind2<tree4[no*2+2].size()){
			tree4[no].pb(tree4[no*2+2][ind2]);
			ind2+=1;
		}
	}
/*	cout<<l<<":"<<r<<endl;
	for(auto j:tree4[no]){
		cout<<j.a<<"<"<<j.b<<endl;
	}*/
	return ;
}

void update(int no,int l,int r,int i,int col){
	if(l==r){
	}
	else{
		int 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);
	}
}

int query(int no,int l,int r,int aa,int bb,int val,int col){
	if(r<aa or l>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		//return -1;
		/*for(int i=l;i<=r;i++){
			if(i<r-1){
				if(tree[no][i-l].a>tree[no][i-l+1].a){
					while(true){
						continue;
					}
				}
			}
		}
		for(int i=l;i<=r;i++){

			if(tree[no][i-l].a>val and vis[tree[no][i-l].b]==0){
				return tree[no][i-l].b;
			}
		}
		if(col==1){
			if(tree2[no]>val){
				st=1;
			}
		}
		if(col==2){
			if(tree3[no]>val){
				st=1;
			}
		}
		return -1;*/
		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;
		}
		/*if(vis[tree[no].back().b]){
			while(true){
				continue;
			}
		}*/
		return tree[no].back().b;
	}
	else{
		int mid=(l+r)/2;
		int 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);
	}
}
int query2(int no,int l,int r,int aa,int bb,int val,int col){
	if(r<aa or l>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		//return -1;
		/*for(int i=l;i<=r;i++){
			if(tree4[no][i-l].a<val and vis[tree4[no][i-l].b]==0){
		//		cout<<val<<","<<tree4[no][i-l].b<<","<<l<<","<<r<<":"<<tree4[no].size()<<endl;
				return tree4[no][i-l].b;
			}
		}
		if(col==1){
			if(tree5[no]<val){
				st=1;
			}
		}
		if(col==2){
			if(tree6[no]<val){
				st=1;
			}
		}
		return -1;*/

		while(tree4[no].size()){
			if(vis[tree4[no].back().b]){
				tree4[no].pop_back();
				continue;
			}
			break;
		}
		if(col==1){
			if(tree5[no]<val){
				st=1;
			}
		}
		if(col==2){
			if(tree6[no]<val){
				st=1;
			}
		}


		if(tree4[no].size()==0){
			return -1;
		}
		if(tree4[no].back().a>=val){
			return -1;
		}

		return tree4[no].back().b;
	}
	else{
		int mid=(l+r)/2;
		int x=query2(no*2+1,l,mid,aa,bb,val,col);
		if(x!=-1){
			return x;
		}
		return query2(no*2+2,mid+1,r,aa,bb,val,col);
	}
}
void update2(int no,int l,int r,int i,int col){
	if(l==r){
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i,col);
		}
		else{
			update2(no*2+2,mid+1,r,i,col);
		}
	}
	if(col==1){
		tree5[no]=min(tree5[no],cc[i].a.b);
	}
	else{
		tree6[no]=min(tree6[no],cc[i].a.b);
	}
}

void dfs(int no,int col=1){
	vis[no]=col;
	//cout<<no<<endl;
	update(0,0,n-1,no,col);
	update2(0,0,n-1,ind[no],col);
	//cout<<no<<endl;
	int low=no;
	int high=n-1;
	while(low<high-1){
		int mid=(low+high)/2;
		if(ac[mid].a<=ac[no].b){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	int ind2=low;
	if(ac[high].a<=ac[no].b){
		ind2=max(ind2,high);
	}
	while(true){
		int x=query(0,0,n-1,no,ind2,ac[no].b,col);//add details
		if(x==-1){
			break;
		}
		dfs(x,3-col);
	}
	low=0;
	high=ind[no];
	while(low<high-1){
		int mid=(low+high)/2;
		if(cc[mid].a.a>=ac[no].a){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	ind2=high;
	if(cc[low].a.a>=ac[no].a){
		ind2=min(ind2,low);
	}
	//cout<<ind2<<','<<ind[no]<<":"<<no<<endl;
	while(true){
		int x=query2(0,0,n-1,ind2,ind[no],ac[no].a,col);//add details
	//	cout<<no<<','<<ind2<<","<<ind[no]<<endl;
		if(x==-1){
			break;
		}
		dfs(x,3-col);
	}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int 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(int i=0;i<n;i++){
		cc.pb({{ac[i].b,ac[i].a},i});

	}
	sort(cc.begin(),cc.end());
	for(int i=0;i<n;i++){
		ind[cc[i].b]=i;
	}
/*	for(auto j:cc){
		cout<<j.a.a<<","<<j.a.b<<","<<j.b<<endl;
	}*/

	/*for(int i=0;i<n;i++){
		ind[ac[i].b]=i;
	}*/


/*	for(int i=0;i<n;i++){
		for(int 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);
	build2(0,0,n-1);
	int co=0;
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
			co+=1;
		}
	}
	if(st){
		cout<<0<<endl;
	}
	else{
		llo ans=1;
		for(int i=0;i<co;i++){
			ans*=2;
			ans%=mod;
		}
		cout<<ans<<endl;

	}








	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void build(int, int, int)':
port_facility.cpp:38: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:38: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:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree[no*2+1].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp:52:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<tree[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void build2(int, int, int)':
port_facility.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree4[no*2+1].size() and ind2<tree4[no*2+2].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:70:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree4[no*2+1].size() and ind2<tree4[no*2+2].size()){
                                      ~~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:80:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<tree4[no*2+1].size()){
         ~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<tree4[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~~~~

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