Submission #373090

#TimeUsernameProblemLanguageResultExecution timeMemory
373090SeanliuPort Facility (JOI17_port_facility)C++14
0 / 100
1 ms364 KiB
#include <iostream>
#include <numeric>
#define int long long int
using namespace std;


const int maxN = 2e5 + 326, MOD = 1e9 + 7;
int N, A[maxN], B[maxN];

struct DSU{
	int dsu[maxN], sz[maxN];
	DSU(){}
	void init(int N){
		iota(dsu, dsu + N + 1, 0);
		fill(sz, sz + N + 1, 1);
	}
	void Flat(int x){
		if(x == dsu[x]) return;
		Flat(dsu[x]);
		sz[x] = sz[dsu[x]];
		dsu[x] = dsu[dsu[x]];
	}
	inline bool Merge(int a, int b){
		Flat(a);
		Flat(b);
		if(dsu[a] == dsu[b]) return false;
		sz[dsu[a]] += sz[dsu[b]];
		dsu[dsu[b]] = dsu[a];
		return true;
	}
} dsu;

bool intersect(int a, int b){
	if(A[a] > A[b]) swap(a, b);	
	return A[b] < B[a] && B[b] > B[a];
}

inline int mpow(int b, int e){
	int r = 1;
	for(int i = 0; i < 60; i++){
		if((e >> i) & 1) r = r * b % MOD;
		b = b * b % MOD;
	}
	return r;
}

signed main(){
	cin >> N;
	dsu.init(2 * N);
	if(N > 2000) return 0;
	for(int i = 0; i < N; i++){
		cin >> A[i] >> B[i];
		for(int j = 0; j < i; j++) if(intersect(i, j)){
			if(dsu.Merge(i, j + N) && dsu.Merge(i + N, j)) continue;
			else {
				cout << 0 << endl;
				return 0;
			}
		}
	}
	int ans = 1;
	for(int i = 0; i < N; i++){
		dsu.Flat(i);
		dsu.Flat(i + N);
		if(dsu.dsu[i] == i) ans++;
		if(dsu.dsu[i + N] == i + N) ans++;
	}
	cout << mpow(2, ans / 2) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...