Submission #1255790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255790		shafi_root	Port Facility (JOI17_port_facility)	C++20	78 / 100	1289 ms	325824 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    = 2e5  + 5;
const int LOG    = 23;

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<pair<int, bool>> 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 (pii u : adj[v]) {
		if (valid[u.F] && !mark[u.F]) {
			col[u.F] = col[v] ^ u.S;
			dfs(u.F);
		}
		else if (valid[u.F] && col[v] != (col[u.F]^u.S)) 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, 0});
	adj[N].pb({y, 0});
	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, 1});
		adj[x].pb({id, 1});
		return;
	}
	if (s < mid) AddE(s,e,x, l, mid, adj[id][0].F);
	if (mid < e) AddE(s,e,x, mid, r, adj[id][1].F);
}

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].F, H+1);
		++N;
		adj[N].pb({x, 0});
		adj[N].pb({adj[id][1].F, 0});
	}
	else {
		int x = Rem(s, mid, r, adj[id][1].F, H+1);
		++N;
		adj[N].pb({adj[id][0].F, 0});
		adj[N].pb({x, 0});
	}
	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[adj[j][0].F] |= valid[j];
			valid[adj[j][1].F] |= valid[j];
		}
	}
	for (int i = n + 1; i <= N; i++) {
		if (valid[i]) {
			adj[adj[i][0].F].pb({i, 0});
			adj[adj[i][1].F].pb({i, 0});
			// cout << i << ' ' << adj[i][0].F << '\n';
			// cout << i << ' ' << adj[i][1].F << '\n';
		}
	}
	// for (int i = 1; i <= n; i++) {
	// 	for (pii 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[adj[j][0].F] && !valid[adj[j][1].F]) 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: 56 / 56
• Subtask 4: 0 / 22