제출 #648419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648419		ymm	Port Facility (JOI17_port_facility)	C++17	100 / 100	871 ms	134252 KiB

port_facility

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1'000'010;
int con_l[N], con_r[N];
int par[N];
int sz[N];
int n;

struct con_cmp {
	bool operator()(int i, int j)
	{
		return con_r[i] > con_r[j];
	}
};
typedef priority_queue<int, vector<int>, con_cmp> con_heap;

con_heap nodes[N][2];

void merge(int v, int u, bool parity)
{
	if (nodes[v][0].size() < nodes[u][parity].size())
		nodes[v][0].swap(nodes[u][parity]);
	for (int x : *(vector<int> *)&nodes[u][parity])
		nodes[v][0].push(x);
	{ con_heap tmp; tmp.swap(nodes[u][parity]); }
	// ------------- //
	if (nodes[v][1].size() < nodes[u][!parity].size())
		nodes[v][1].swap(nodes[u][!parity]);
	for (int x : *(vector<int> *)&nodes[u][!parity])
		nodes[v][1].push(x);
	{ con_heap tmp; tmp.swap(nodes[u][!parity]); }
}

bool set_root(int &v)
{
	bool ans = 0;
	while (par[v] != -1) {
		v = par[v];
		ans ^= 1;
	}
	return ans;
}

int unite(int v, int u, bool parity)
{
	parity ^= set_root(v);
	parity ^= set_root(u);
	if (sz[v] < sz[u])
		swap(v, u);
	par[u] = v;
	sz[v] += sz[u];
	merge(v, u, parity);
	return v;
}

struct com_cmp {
	bool operator()(int i, int j)
	{
		int x0 = nodes[i][0].size()? con_r[nodes[i][0].top()]: 2*N;
		int x1 = nodes[i][1].size()? con_r[nodes[i][1].top()]: 2*N;
		int y0 = nodes[j][0].size()? con_r[nodes[j][0].top()]: 2*N;
		int y1 = nodes[j][1].size()? con_r[nodes[j][1].top()]: 2*N;
		int x = min(x0, x1);
		int y = min(y0, y1);
		return x > y || (x == y && i > j);
	}
};
priority_queue<int, vector<int>, com_cmp> coms;

int solve()
{
	Loop (i,0,n) {
		nodes[i][0].push(i);
		int l = con_l[i], r = con_r[i];
		int waiting_com = i;
		for (;;) {
			if (!coms.size())
				break;
			int com = coms.top();
			bool pre_even =    nodes[com][0].size()
			                && con_r[nodes[com][0].top()] < r;
			bool pre_odd  =    nodes[com][1].size()
			                && con_r[nodes[com][1].top()] < r;
			if (!pre_even && !pre_odd)
				break;
			coms.pop();
			while (   nodes[com][0].size()
			       && con_r[nodes[com][0].top()] < l) {
				nodes[com][0].pop();
			}
			while (   nodes[com][1].size()
			       && con_r[nodes[com][1].top()] < l) {
				nodes[com][1].pop();
			}
			bool even =    nodes[com][0].size()
			            && con_r[nodes[com][0].top()] < r;
			bool odd  =    nodes[com][1].size()
			            && con_r[nodes[com][1].top()] < r;
			if (even && odd) {
				cout << "0\n";
				exit(0);
			} else if (even) {
				waiting_com = unite(waiting_com, com, 1);
			} else if (odd) {
				waiting_com = unite(waiting_com, com, 0);
			} else {
				coms.push(com);
			}
		}
		coms.push(waiting_com);
	}
	return coms.size();
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	vector<pii> vec;
	Loop (i,0,n) {
		int x, y;
		cin >> x >> y;
		vec.push_back({x, y});
	}
	sort(vec.begin(), vec.end());
	Loop (i,0,n)
		tie(con_l[i], con_r[i]) = vec[i];
	memset(par, -1, sizeof(par));
	int ans = solve();
	int p2ans = 1;
	while (ans--)
		p2ans = p2ans*2 % 1'000'000'007;
	cout << p2ans << '\n';
}

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