제출 #1255801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255801		shafi_root	Port Facility (JOI17_port_facility)	C++20	22 / 100	810 ms	1080260 KiB

port_facility

/* _In The Name Of God_ */

#include <bits/stdc++.h>
using namespace std;

#define maxs(a, b)			a = max(a, b)
#define mins(a, b)			a = min(a, b)
#define pb						push_back
#define F						first
#define S						second
#define mid						((l + r)/2)
// #define int                     long long

typedef pair<int, int>     	pii;
typedef long long               	ll;

const ll  MOD    = 1e9  + 7; // 998244353;
const ll  INF    = 1e9  + 1;
const int MXN    = 2e6  + 5;
const int LOG    = 21;

ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }

int n, N, Root, R[MXN], p[MXN];
vector<int> adj[MXN*LOG];
vector<int> h[LOG];
bool mark[MXN*LOG], valid[MXN*LOG], col[MXN*LOG];
ll ans = 1;

void dfs(int v) {
	mark[v] = 1;
	// cout << v << '\n';
	for (int u : adj[v]) {
		int o = u < 0, j = abs(u);
		if (valid[j] && !mark[j]) {
			col[j] = col[v] ^ o;
			dfs(j);
		}
		else if (valid[j] && col[v] != (col[j]^o)) ans = 0;
	}
}

int Build(int l=1, int r=2*n+1, int H = 0) {
	if (r - l < 2) {
		return p[l];
	}
	int x = Build(l, mid, H+1);
	int y = Build(mid, r, H+1);
	++N; //lc[N] = x, rc[N] = y;
	adj[N].pb(x);
	adj[N].pb(y);
	h[H].pb(N);
	return N;
}

void AddE(int s, int e, int x, int l=1, int r=2*n+1, int id = Root) {
	if (s <= l && r <= e) {
		adj[id].pb(-x);
		adj[x].pb(-id);
		return;
	}
	if (s < mid) AddE(s,e,x, l, mid, adj[id][0]);
	if (mid < e) AddE(s,e,x, mid, r, adj[id][1]);
}

int Rem(int s, int l = 1, int r=2*n+1, int id = Root, int H = 0) {
	if (r - l < 2) {
		return 0;
	}
	if (s < mid) {
		int x = Rem(s, l, mid, adj[id][0], H+1);
		++N;
		adj[N].pb(x);
		adj[N].pb(adj[id][1]);
	}
	else {
		int x = Rem(s, mid, r, adj[id][1], H+1);
		++N;
		adj[N].pb(adj[id][0]);
		adj[N].pb(x);
	}
	h[H].pb(N);
	return N;
}

void _solve() {
    cin >> n;
	N = n;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		R[r] = l;
		p[l] = i;
	}
	Root = Build();
	for (int i = 1; i <= 2*n; i++) {
		if (R[i]) {
			AddE(R[i]+1, i+1, p[R[i]]);
			Root = Rem(R[i]);
		}
	}
	fill(valid+1, valid+n+1, 1);
	for (int i = 0; i < LOG; i++) {
		for (int j : h[i]) {
			if (adj[j].size() > 2)
				valid[j] = 1;
			valid[abs(adj[j][0])] |= valid[j];
			valid[abs(adj[j][1])] |= valid[j];
		}
	}
	for (int i = n + 1; i <= N; i++) {
		if (valid[i]) {
			adj[abs(adj[i][0])].pb(i);
			adj[abs(adj[i][1])].pb(i);
			// cout << i << ' ' << adj[i][0].F << '\n';
			// cout << i << ' ' << adj[i][1].F << '\n';
		}
	}
	// for (int i = 1; i <= n; i++) {
	// 	for (int j : adj[i]) cout << i << ' ' << j.F << '\n';
	// }
	valid[0] = 0;
	for (int i = LOG-1; i >= 0; i--) {
		for (int j : h[i]) {
			if (valid[j] && !valid[abs(adj[j][0])] && !valid[abs(adj[j][1])]) valid[j] = 0;
		}
	}
	// cout << '\n';
	for (int i = 1; i <= n; i++) {
		if (!mark[i] && valid[i]) dfs(i), (ans *= 2) %= MOD;
	}
	cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--) _solve();
    return 0.0;
}

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