Submission #1128816

#TimeUsernameProblemLanguageResultExecution timeMemory
1128816Rainmaker2627Port Facility (JOI17_port_facility)C++20
22 / 100
6093 ms16052 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long

struct dsu {
	int n, cc;
	vector<int> r, s, d;

	dsu(int n) {
		this->n=n; cc=n;
		r.reserve(n+1);
		for (int i = 1; i <= n; ++i) r[i]=i;
		s.assign(n+1, 1);
		d.assign(n+1, 0);
	}

	int find(int a) {
		if (a==r[a]) return a;
		int p=find(r[a]);
		d[a]^=d[r[a]];
		return r[a]=p;
	}

	bool unite(int a, int b) {
		int ra=find(a), rb=find(b);
		if (ra==rb) return d[a]^d[b]==1;
		if (s[ra]<s[rb]) swap(ra, rb);
		d[rb]=1^d[a]^d[b];
		r[rb]=ra; s[ra]+=s[rb]; cc--;
		return true;
	}
};

int exp(int a, int b, int mod) {
	int x=1;
	while (b) {
		if (b%2) x=(x*a)%mod;
		a=(a*a)%mod; b/=2;
	} return x;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);

	int n;
	cin >> n;
	vector<pair<int, int>> s;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		s.push_back({a[i], i+1});
		s.push_back({b[i], -i-1});
	} sort(s.begin(), s.end());

	dsu uf(n+1);
	vector<list<int>> mt;
	for (auto i = 0; i < 2*n; ++i) {
		int j = s[i].second;
		if (j>0) mt.push_back({j});
		else {
			j=-j;
			list<int> tmp;
			while (true) {
				if (mt.size()==0) { cout << "0\n"; return 0; }
				if (mt.back().back()==j) {
					mt.back().pop_back();
					if (mt.back().size()==0) mt.pop_back();
					break;
				}
				if (!uf.unite(j, mt.back().back())) { cout << "0\n"; return 0; }
				tmp.splice(tmp.begin(), mt.back());
				mt.pop_back();
			}
			if (tmp.size()) mt.push_back(tmp);
		}
	}

	cout << exp(2, uf.cc-1, 1e9+7) << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...