제출 #727592

#제출 시각아이디문제언어결과실행 시간메모리
727592qwerasdfzxclPort Facility (JOI17_port_facility)C++17
0 / 100
7 ms15976 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int MOD = 1e9+7;

pair<int, int> operator + (const pair<int, int> &x, const pair<int, int> &y){return pair<int, int>(x.first + y.first, x.second + y.second);}
pair<int, int> operator - (const pair<int, int> &x, const pair<int, int> &y){return pair<int, int>(x.first - y.first, x.second - y.second);}

struct Seg{
	pair<int, int> tree[2002000];
	int sz;
	void init(int n){sz = n;}
	void update(int p, int x){
		pair<int, int> v(1, x);
		while(p<=sz){
			tree[p] = tree[p] + v;
			p += p&-p;
		}
	}
	pair<int, int> sum(int p){
		pair<int, int> ret(0, 0);
		while(p){
			ret = ret + tree[p];
			p -= p&-p;
		}
		return ret;
	}
	int query(int l, int r){
		auto p = sum(r) - sum(l-1);
		if (p.second==0) return 1;
		if (p.second==p.first) return 0;
		return -1;
	}
}tree;

struct DSU{
	int path[2002000], R[2002000], c;
	void init(int n){c = n; for (int i=1;i<=n;i++) path[i] = R[i] = i;}
	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}
	void merge(int s, int v){
		s = find(s), v = find(v);
		if (s==v) return;
		--c;
		path[s] = v;
		R[v] = max(R[v], R[s]);
	}
	int r(int x){return R[find(x)];}
}dsu;
int a[2002000];

ll pw(ll a, ll e){
	if (!e) return 1;
	ll ret = pw(a, e/2);
	if (e&1) return ret * ret % MOD * a % MOD;
	return ret * ret % MOD;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	cin >> n;
	tree.init(n*2);
	dsu.init(n*2);

	for (int i=1;i<=n;i++){
		int x, y;
		cin >> x >> y;
		a[x] = y;
		a[y] = x;
		dsu.merge(x, y);
	}

	for (int i=1;i<=n*2;i++) if (i < a[i]){
		for (int j=i+1;j<=n*2;j++) if (j < a[j]){
			if (i < j && j < a[i] && a[i] < a[j]){
				dsu.merge(i, j);
			}
		}
	}

	// vector<int> st;
	// for (int i=1;i<=n*2;i++){
	// 	while(!st.empty() && st.back() < i) st.pop_back();
		
	// 	if (i < a[i]){
	// 		int col = tree.query(i, a[i]);
	// 		if (col==-1){
	// 			printf("0\n");
	// 			return 0;
	// 		}
	// 		tree.update(a[i], col);
	// 		st.push_back(a[i]);
	// 	}

	// 	else{
	// 		int R = dsu.r(i);
	// 		while(!st.empty() && st.back() != R){
	// 			dsu.merge(i, st.back());
	// 			st.pop_back();
	// 		}
	// 		st.back() = dsu.r(i);
	// 	}
	// 	assert(st.back()==dsu.r(i));

	// }

	printf("%lld\n", pw(2, dsu.c));
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...