제출 #30972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30972		szawinis	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	2188 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;
set<pair<int,int> > st;

int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[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;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	dsu.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, l, r; i < n; i++) {
		tie(l, r) = a[i];
		auto it = st.upper_bound(make_pair(r, INT_MAX));
		if(it == st.begin()) {
			st.emplace(r, i);
			continue;
		}
		--it;
		if(it->first > l) merge(i, it->second);
		while(it != st.begin() && prev(it) != st.begin() && prev(it)->first > l) {
			merge(i, prev(it)->second);
			it = prev(st.erase(prev(it)));
		}
		if(it != st.begin() && prev(it)->first > l) {
			merge(i, prev(it)->second);
			st.erase(prev(it));
		}
		st.emplace(r, i);
	}
	int cc = 0;
	for(int i = 0; i < n; i++) cc += dsu[i] < 0;
	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