제출 #656009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656009		Farbod	Port Facility (JOI17_port_facility)	C++17	0 / 100	24 ms	47248 KiB

port_facility

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Sun, 06 Nov 2022 (12:08:19)
*
*/
#include <iostream>
#include <vector>
using namespace std;

const int N = 2e6 + 5;
const long long mod = 1e9 + 7;

int n, l[N], r[N], a[N];

bool vis[N], out[N];
int sz[N], par[N];
vector <int> adj[N], v;

long long pw(int a, int r)
{
	if (r == 0)
		return 1;
	if (r == 1)
		return a;

	long long c = pw(a, r / 2);
	return c * c % mod * pw(a, r % 2) % mod;
}

int get(int v)
{
	if (v == par[v])
		return v;
	return par[v] = get(par[v]);
}

vector <int> vec;

void merge(int u, int v)
{
	u = get(u), v = get(v);

	for (auto x: adj[v])
		vec.push_back(x);

	par[v] = u, sz[u] += sz[v];

	return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];

		a[l[i]] = i, a[r[i]] = -i;
	}

	for (int i = 1; i <= 2 * n; i++) {
		if (a[i] > 0) {
			par[a[i]] = a[i], sz[a[i]] = 1, adj[a[i]].push_back(a[i]), v.push_back(a[i]);
			continue;
		}

		while (out[adj[get(-a[i])].back()])
			adj[get(-a[i])].pop_back();

		if (adj[get(-a[i])].back() != -a[i])
			return cout << 0, 0;

		while (v.back() != get(-a[i])) {
			merge(get(-a[i]), v.back());

			if (sz[v.back()] > 1)
				return cout << 0, 0;

			v.pop_back();
		}

		while (vec.size())
				adj[get(-a[i])].push_back(vec.back()), vec.pop_back();

		sz[get(-a[i])]--;
		if (sz[get(-a[i])] == 0)
			v.pop_back();

		out[-a[i]] = 1;
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (!vis[get(i)])
			vis[get(i)] = 1, ans++;

	cout << pw(2, ans);

    return 0;
}

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