Submission #655984

#	Time	Username	Problem	Language	Result	Execution time	Memory
655984		mosaev	Port Facility (JOI17_port_facility)	C++17	78 / 100	5858 ms	649728 KiB

port_facility

#include <bits/stdc++.h>
#include <set>
#include <unordered_map>
using namespace std;
#define ll long long
#define N (ll)(1e6+5)
#define NP (2097155ll)
#define M ((ll)1e9+7)
#define fi first
#define se second
ll ans;
int n, ft[N], s[N], t[N * 2], grp[N], p[N], cnt;
vector<int> v[N];
unordered_map<int, unsigned char> seg[NP], st;
bool seen[N];
inline void get(ll l, ll r) {
	l += 1048575ll, r += 1048575ll; st.clear();
	while (l <= r) {
		if (l & 1) { for (auto x : seg[l]) st[x.first] |= x.second; l++; }
		if (!(r & 1)) { for (auto x : seg[r]) st[x.first] |= x.second; r--; }
		l >>= 1, r >>= 1;
	}
}
inline void upd(ll x, ll a, ll b, ll c) {
	x += 1048575ll;
	while (x > 0) {
		seg[x].erase(a); seg[x][b] |= c;
		x >>= 1;
	}
}
inline void merge(ll a, ll b, ll c) {
	c &= grp[a]; a = p[a]; if (v[a].size() < v[b].size()) swap(a, b);
	for (auto x : v[b]) {
		p[x] = a; v[a].push_back(x);
		if (c) grp[x] ^= 3;
		upd(ft[x], b, a, grp[x]);
	}v[b].clear();
	cnt--;
}
int main() {
#define int ll
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll a, b; cin >> n; for (int i = 1; i <= n; i++) cin >> a >> b, ft[i] = b, t[a] = t[b] = i, p[i] = i, v[i].push_back(i), grp[i] = 1; cnt = n;
  assert(n < 1000000);
	b = 1; for (int i = 1; i <= 2 * n; i++) {
		a = t[i];
		if (ft[a] == i) ft[a] = b++;
		else s[a] = b;
	}
	for (int i = 1; i <= 2 * n; i++) {
		a = t[i]; if (seen[a]) continue; seen[a] = true;
		get(s[a], ft[a]);
		for (auto x : st) {
			if (x.second == 3) return cout << 0 << '\n', 0;
			merge(a, x.first, x.second);
		}
		upd(ft[a], 0, p[a], grp[a]);
	}
	ans = 1; for (int i = 1; i <= cnt; i++) ans <<= 1, ans %= M;
	cout << ans;
}

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