Submission #535201

#	Time	Username	Problem	Language	Result	Execution time	Memory
535201		pnm1384	Port Facility (JOI17_port_facility)	C++14	100 / 100	4103 ms	173652 KiB

port_facility

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

typedef long long ll;
int mod = 1e9 + 7;

#define F first
#define S second

const int N = 2e6 + 20, inf = 3e7;
pair<int, int> a[N], b[N], seg[N << 2][2];
int n;
bool visited[N];
int col[N];
stack<int> st;

void build(int u = 1, int s = 0, int e = N)
{
	seg[u][0] = {inf, s}; seg[u][1] = {-inf, s};
	if (e - s < 2) return;
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	build(lc, s, mid); build(rc, mid, e);
	return;
}

void add(int ind, int ff, int x, int u = 1, int s = 0, int e = 2 * n)
{
	if (e - s < 2)
	{
		seg[u][ff] = {x, s};
		return;
	}
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	if (ind < mid)
		add(ind, ff, x, lc, s, mid);
	else 
		add(ind, ff, x, rc, mid, e);
	if (ff == 0) seg[u][ff] = min(seg[lc][ff], seg[rc][ff]);
	else seg[u][ff] = max(seg[lc][ff], seg[rc][ff]);
	return;
}

pair<int, int> get(int l, int r, int ff, int u = 1, int s = 0, int e = 2 * n)
{
	if (e <= l || r <= s)
	{
		if (ff == 0) return {inf, s};
		return {-inf, s};
	}
	if (l <= s && r >= e) return seg[u][ff];
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	if (ff == 0) return min(get(l, r, ff, lc, s, mid), get(l, r, ff, rc, mid, e));
	return max(get(l, r, ff, lc, s, mid), get(l, r, ff, rc, mid, e));
}

void dfs(int u)
{
	visited[u] = true;
	int l = a[u].F, r = a[u].S;
	add(r, 0, inf); add(l, 1, -inf);
	if (r - l >= 2)
	{
		while (true)
		{
			pair<int, int> pp = get(l + 1, r, 0);
			if (pp.F >= l) break;
			int ind = b[pp.S].F;
			if (!visited[ind]) 
			{
				col[ind] = 1 - col[u];
				dfs(ind);
			}
		}
		while (true)
		{
			pair<int, int> pp = get(l + 1, r, 1);
			if (pp.F <= r) break;
			int ind = b[pp.S].F;
			if (!visited[ind]) 
			{
				col[ind] = 1 - col[u];
				dfs(ind);
			}
		}
	}
	return;
}

inline bool check(int ff)
{
	while (!st.empty()) st.pop();
	for (int i = 0; i < 2 * n; i++)
	{
		if (col[b[i].F] != ff) continue;
		int x = b[i].F;
		if (b[i].S == 0)
		{
			st.push(x);
			continue;
		}
		if (st.top() != x) return false;
		st.pop();
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	build();
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		l--; r--;
		a[i] = {l, r};
		b[l] = {i, 0}; b[r] = {i, 1};
		add(r, 0, l);
		add(l, 1, r);
	}
	int tt = 0;
	for (int i = 0; i < n; i++)
	{
		if (!visited[i]) 
		{
			dfs(i);
			tt++;
		}
	}
	if ((!check(0)) || (!check(1))) cout << 0;
	else
	{
		int ans = 1;
		for (int i = 0; i < tt; i++) ans = 1ll * ans * 2 % mod;
		cout << ans;
	}
	return 0;
}

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