Submission #727587

#	Time	Username	Problem	Language	Result	Execution time	Memory
727587		qwerasdfzxcl	Port Facility (JOI17_port_facility)	C++17	0 / 100	7 ms	15956 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) 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);
	} 

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

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