Submission #727599

#	Time	Username	Problem	Language	Result	Execution time	Memory
727599		qwerasdfzxcl	Port Facility (JOI17_port_facility)	C++17	100 / 100	1048 ms	210648 KiB

port_facility

#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 && p.first) return 1;
		else if (p.second==0) return -2;
		
		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;
vector<int> adj[2002000];
int a[2002000], visited[2002000], col[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;
}

void dfs(int s, int pa = 0){
	col[a[s]] = col[s];
	visited[s] = 1;
	for (auto &v:adj[s]) if (v!=pa){
		col[v] = col[s] ^ 1;
		dfs(v, s);
	}
}

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);
	} 

	vector<int> st;
	for (int i=1;i<=n*2;i++){
		while(!st.empty() && st.back() < i) st.pop_back();
		
		if (i < a[i]){
			st.push_back(a[i]);
		}

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

	for (int i=1;i<=n*2;i++) if (a[i] < i && !visited[i]) dfs(i);
	for (int i=1;i<=n*2;i++) if (i < a[i]){
		int tmp = tree.query(i, a[i]);
		if (tmp!=col[i] && tmp!=-2){
			printf("0\n");
			return 0;
		}
		tree.update(a[i], col[i]);
	}

	printf("%lld\n", pw(2, dsu.c));
}

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