Submission #1299427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299427		kian2009	Port Facility (JOI17_port_facility)	C++20	100 / 100	2622 ms	121460 KiB

port_facility

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

const int MAXN = 2e6 + 10, mod = 1e9 + 7;

int n, ans = 1, a[MAXN], b[MAXN], seen[MAXN], ind[MAXN], seg1[4 * MAXN], seg2[4 * MAXN];
bool is[MAXN];
vector<int> s1, s2;


void make1(int u, int l, int r) {
	seg1[u] = -1;
	if (r - l == 1)
		return;
	int mid = (l + r) / 2;
	make1(2 * u, l, mid);
	make1(2 * u + 1, mid, r);
}

void make2(int u, int l, int r) {
	seg2[u] = MAXN;
	if (r - l == 1)
		return;
	int mid = (l + r) / 2;
	make2(2 * u, l, mid);
	make2(2 * u + 1, mid, r);	
}

void upd1(int u, int l, int r, int i, int x) {
	if (i < l || i >= r)
		return;
	if (r - l == 1) {
		seg1[u] = x;
		return;
	}
	int mid = (l + r) / 2;
	upd1(2 * u, l, mid, i, x);
	upd1(2 * u + 1, mid, r, i, x);
	seg1[u] = max(seg1[2 * u], seg1[2 * u + 1]);
}

void upd2(int u, int l, int r, int i, int x) {
	if (i < l || i >= r)
		return;
	if (r - l == 1) {
		seg2[u] = x;
		return;
	}
	int mid = (l + r) / 2;
	upd2(2 * u, l, mid, i, x);
	upd2(2 * u + 1, mid, r, i, x);
	seg2[u] = min(seg2[2 * u], seg2[2 * u + 1]);
}

int get1(int u, int l, int r, int s, int e) {
	if (s <= l && r <= e)
		return seg1[u];
	if (e <= l || r <= s)
		return -1;
	int mid = (l + r) / 2;
	return max(get1(2 * u, l, mid, s, e), get1(2 * u + 1, mid, r, s, e));	
}

int get2(int u, int l, int r, int s, int e) {
	if (s <= l && r <= e)
		return seg2[u];
	if (e <= l || r <= s)
		return MAXN;
	int mid = (l + r) / 2;
	return min(get2(2 * u, l, mid, s, e), get2(2 * u + 1, mid, r, s, e));	
}


void input() {
	cin >> n;
	for (int i = 1; i <= 2 * n; i++)
		ind[i] = -1;
	make1(1, 1, 2 * n + 1);
	make2(1, 1, 2 * n + 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		ind[a[i]] = ind[b[i]] = i;
		is[a[i]] = true;
		upd1(1, 1, 2 * n + 1, a[i], b[i]);
		upd2(1, 1, 2 * n + 1, b[i], a[i]);
	}
}

void dfs(int u) {
	upd1(1, 1, 2 * n + 1, a[u], -1);
	upd2(1, 1, 2 * n + 1, b[u], MAXN);
	int x = get1(1, 1, 2 * n + 1, a[u], b[u]);
	while (x > b[u]) {
		int v = ind[x];
		seen[v] = 3 - seen[u];
		dfs(v);
		x = get1(1, 1, 2 * n + 1, a[u], b[u]);
	}
	x = get2(1, 1, 2 * n + 1, a[u], b[u]);
	while (x < a[u]) {
		int v = ind[x];
		seen[v] = 3 - seen[u];
		dfs(v);
		x = get2(1, 1, 2 * n + 1, a[u], b[u]);	
	}
}

void findAns() {
	for (int i = 0; i < n; i++)
		if (!seen[i]) {
			seen[i] = 1;
			dfs(i);
			ans = (ans * 2) % mod;
		}
}

bool check() {
	for (int i = 1; i <= 2 * n; i++) {
		if (ind[i] == -1)
			continue;
		if (is[i]) {
			if (seen[ind[i]] == 1)
				s1.push_back(ind[i]);
			else
				s2.push_back(ind[i]);	
		}
		else {
			if (seen[ind[i]] == 1) {
				if (s1.empty() || s1.back() != ind[i])
					return true;
				s1.pop_back();	
			}
			else {
				if (s2.empty() || s2.back() != ind[i])
					return true;
				s2.pop_back();	
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	findAns();
	cout << (check()? 0: ans) << endl;
	return 0;
}

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