Submission #97544

#	Time	Username	Problem	Language	Result	Execution time	Memory
97544		silxikys	Port Facility (JOI17_port_facility)	C++14	100 / 100	1532 ms	84796 KiB

port_facility

#include <bits/stdc++.h>
 
#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007LL
 
using namespace std;
 
int N; lld ans,inv;
struct data{
	int x,y;
	bool operator < (const data &cmp) const{
		if(x != cmp.x) return x < cmp.x;
		return y < cmp.y;
	}
}a[1000002];
int par[2000002];
map<int,int> Map;
 
void impossible(){puts("0");exit(0);}
int getpar(int x){return (x == par[x])?x:(par[x]=getpar(par[x]));};
void merge(int x,int y){
	x = getpar(x); y = getpar(y);
	par[x] = y;
}
void uni(int x,int y){
	merge(x,y+N); merge(x+N,y);
	if(getpar(x) == getpar(x+N) || getpar(y) == getpar(y+N)) impossible();
}
 
int main(){
	scanf("%d",&N); ans = 1;
	for(int i=1; i<=N; i++){
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+N+1);
	iota(par+1,par+N*2+1,1);
	for(int i=1; i<=N; i++){
		auto it1 = Map.lower_bound(a[i].x);
		auto it2 = Map.lower_bound(a[i].y);
		while(it1 != it2){
			uni(it1->second,i);
			auto it = it2; it--;
			if(it != it2 && getpar(it->second) == getpar(it1->second)) break;
			it1++;
		}
		Map[a[i].y] = i;
	}
	for(int i=1; i<=N; i++){
		if(getpar(i) == i){
			ans *= 2; ans %= Mod;
		}
	}
	printf("%lld\n",ans);
 
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N); ans = 1;
  ~~~~~^~~~~~~~~
port_facility.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].x,&a[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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