Submission #982607

#	Time	Username	Problem	Language	Result	Execution time	Memory
982607		AmirAli_H1	Port Facility (JOI17_port_facility)	C++17	100 / 100	3219 ms	222736 KiB

port_facility

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

struct node {
	pair<pii, int> val1, val2;
};

int n;
const int maxn = 2e6 + 4;
const int mod = 1e9 + 7;
pii A[maxn]; int ind[maxn], num;
pii p[maxn]; vector<int> ls[maxn];
node t[4 * maxn], ca;

ll power(ll a, ll b) {
	if (b == 0) return 1;
	return power(a * a % mod, b / 2) * ((b & 1) ? a : 1) % mod;
}

node f(node a, node b) {
	node res = a;
	for (auto x : {b.val1, b.val2}) {
		if (x.S != -1) {
			if (res.val1.S == -1 || x.F != res.val1.F) {
				res.val2 = res.val1; res.val1 = x;
			}
		}
	}
	return res;
}

void build(int v, int tl, int tr) {
	t[v] = ca;
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

void set_val(int v, int tl, int tr, int i, pair<pii, int> x) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v].val1 = x;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_val(2 * v + 1, tl, mid, i, x); set_val(2 * v + 2, mid, tr, i, x);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

node get_res(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ca;
	if (l == tl && r == tr) return t[v];
	int mid = (tl + tr) / 2;
	return f(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r));
}

void merge(int u1, int u2) {
	pii a = p[u1], b = p[u2];
	if (a.F == b.F) {
		if (a.S == b.S) kill(0);
		return ;
	}
	num--;
	if (len(ls[a.F]) > len(ls[b.F])) swap(a, b);
	
	int r = (a.S == b.S);
	for (int v : ls[a.F]) {
		p[v].F = b.F; p[v].S ^= r;
		ls[b.F].pb(v);
		set_val(0, 0, 2 * n, A[v].F, Mp(p[v], v));
	}
	ls[a.F].clear(); ls[a.F].shrink_to_fit();
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	ca.val1 = ca.val2 = Mp(Mp(-1, -1), -1);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i].F >> A[i].S;
		A[i].F--; A[i].S--;
		ind[A[i].F] = i; ind[A[i].S] = i;
	}
	
	num = n;
	for (int i = 0; i < n; i++) {
		p[i] = Mp(i, 0);
		ls[i].pb(i);
	}
	
	build(0, 0, 2 * n);
	for (int j = 2 * n - 1; j >= 0; j--) {
		int i = ind[j];
		if (A[i].S != j) continue;
		auto f = get_res(0, 0, 2 * n, A[i].F + 1, A[i].S);
		while (f.val2.S != -1) {
			merge(i, f.val1.S); merge(i, f.val2.S);
			f = get_res(0, 0, 2 * n, A[i].F + 1, A[i].S);
		}
		if (f.val1.S != -1) merge(i, f.val1.S);
		set_val(0, 0, 2 * n, A[i].F, Mp(p[i], i));
	}
	
	cout << power(2, num) << endl;
	
	return 0;
}

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