Submission #70724

#	Time	Username	Problem	Language	Result	Execution time	Memory
70724		yogahmad	Port Facility (JOI17_port_facility)	C++14	100 / 100	3100 ms	586484 KiB

port_facility

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 2000003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int>ve[mx*4];
pair<int,int>a[mx];
int n,par[mx];

int find(int x){
//	debug(x);
	if(x==par[x])return x;
	return par[x]=find(par[x]);
}

void gabung(int idx,int l,int r,int fl,int fr,int val){
	if(fl>r || fr<l)return;
	if(ve[idx].size()==0)return;
	if(fl<=l && r<=fr){
	//	debug(val);
		for(int i:ve[idx]){
			int j=i;
			if(j<=n)j+=n;
			else j-=n;
			i=find(i);
	//		debug(i);
			j=find(j);
			par[i]=find(val+n);
			par[j]=find(val);
		}
		ve[idx].clear();
		ve[idx].pb(find(val+n));
		return;
	}
	if(!(fl>MID || fr<l))gabung(idx*2,l,MID,fl,fr,val);
	if(!(fl>r || fr<MID+1))gabung(idx*2+1,MID+1,r,fl,fr,val);
}

void upd(int idx,int l,int r,int in,int val){
	ve[idx].pb(find(val));
	if(l==r)return;
	if(in<=MID)upd(2*idx,l,MID,in,val);
	else upd(2*idx+1,MID+1,r,in,val);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].f,&a[i].s);
	sort(a+1,a+n+1);
	for(int i=1;i<=n*2;i++){
		par[i]=i;
	}
	for(int i=1;i<=n;i++){
		gabung(1,1,n*2,a[i].f,a[i].s,i);
		int x=find(i);
		int y=find(i+n);
		if(x==y){
			cout<<0<<endl;
			return 0;
		}
		upd(1,1,n*2,a[i].s,i);
	}
	for(int i=1;i<=n;i++){
	//	debug(i);
		int x=find(i);
		int y=find(i+n);
		if(x==y){
		//	debug(i);
			cout<<0<<endl;
			return 0;
		}
	}
	set<int>isi;
	for(int i=1;i<=n*2;i++){
		isi.insert(find(i));
	}
	int tot=isi.size();
	assert(tot%2==0);
	tot/=2;
	long long jaw=1;
	for(int i=1;i<=tot;i++){
		jaw=jaw*2%MOD;
	}
	cout<<jaw<<endl;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:62:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%d%d",&a[i].f,&a[i].s);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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