제출 #30973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30973		szawinis	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	2184 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1e9)+7;

inline bool chk_comp(pair<int,int> x, pair<int,int> y) {
	return x.first < y.first && x.second < y.second;
}

int n;
long long ans = 1;
vector<pair<int,int> > a, chk;
vector<int> dsu;//, dsu_chk;
set<pair<int,int> > st;

int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
// int root_chk(int v) { return (dsu_chk[v] < 0 ? v : dsu_chk[v] = root_chk(dsu_chk[v])); }
void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) return;
	if(dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}
// void merge_chk(int u, int v) {
// 	if((u = root_chk(u)) == (v = root_chk(v))) return;
// 	assert(dsu_chk[u] < 0 && dsu_chk[v] < 0);
// 	if(dsu_chk[u] > dsu_chk[v]) swap(u, v);
// 	dsu_chk[u] += dsu_chk[v];
// 	dsu_chk[v] = u;
// }
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	dsu.assign(n, -1);
	// dsu_chk.assign(n, -1);
	for(int i = 0, l, r; i < n; i++) {
		cin >> l >> r;
		a.emplace_back(l, r);
		chk.emplace_back(l, r);
	}

	sort(chk.begin(), chk.end());
	for(int i = 0; i < n; i++) {
		auto it1 = upper_bound(chk.begin(), chk.end(), a[i], chk_comp);
		if(it1 == chk.end()) continue;
		auto it2 = upper_bound(chk.begin(), chk.end(), *it1, chk_comp);
		if(it2 == chk.end()) continue;
		if(it2->first < a[i].second) cout << 0, exit(0);
	}

	sort(a.begin(), a.end());

	// for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) {
	// 	if(a[i].first > a[j].first && a[j].second > a[i].first && a[i].second > a[j].second) {
	// 		merge_chk(i, j);
	// 	}
	// }

	for(int i = 0, l, r; i < n; i++) {
		tie(l, r) = a[i];
		while(!st.empty() && st.begin()->first < l) st.erase(st.begin());
		auto lim = st.upper_bound(make_pair(r, INT_MAX));
		if(st.empty() || lim == st.begin()) {
			st.emplace(r, i);
			continue;
		}
		for(auto it = st.begin(); it != lim && root(i) != root(it->second); it++) merge(i, it->second);
		st.emplace(r, i);
	}
	int cc = 0;
	for(int i = 0; i < n; i++) cc += dsu[i] < 0;//, cout << dsu[i] << ' ' << dsu_chk[i] << endl;
	long long base = 2;
	while(cc) {
		if(cc & 1) ans = ans * base % MOD; 
		base = base * base % MOD;
		cc >>= 1;
	}
	cout << ans;
}

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