Submission #1298011

#TimeUsernameProblemLanguageResultExecution timeMemory
1298011arashmemarPort Facility (JOI17_port_facility)C++20
100 / 100
1810 ms710796 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 100, mod = 1e9 + 7;

pair <int, int> a[maxn];
int u[maxn], x[2 * maxn];

struct Node
{
	int L, R, mid;
	pair <int, int> v;
	Node *lc, *rc;

	Node (int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = {0, 0}, lc = rc = NULL;
		return ;
	}

	void init()
	{
		if (R - L == 1)
		{
			v = {a[L].second, L};
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		v = max(lc->v, rc->v);
		return ;
	}

	void init2()
	{
		if (R - L == 1)
		{
			v = {x[L], x[L]};
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init2();
		rc->init2();
		v = max(lc->v, rc->v);
		return ;
	}

	void update (int p, int val = 0)
	{
		if (R - L == 1)
		{
			v = {val, 0};
			return ;
		}
		if (p < mid)
		{
			lc->update(p, val);
		}
		else
		{
			rc->update(p, val);
		}
		v = max(lc->v, rc->v);
		return ;
	}

	pair <int, int> get(int l, int r)
	{
		if (l >= r)
		{
			return {-mod, -mod};
		}
		if (l == L and R == r)
		{
			return v;
		}
		pair <int, int> ret = {-mod, -mod};
		if (l < mid)
		{
			ret = max(ret, lc->get(l, min(r, mid)));
		}
		if (r > mid)
		{
			ret = max(ret, rc->get(max(l, mid), r));
		}
		return ret;
	}
};

Node *root[4];

bool mark[maxn][2];

void dfs(int v, bool s)
{
	if (mark[v][s])
	{
		return ;
	}
	mark[v][s] = 1;
	if (mark[v][s] and mark[v][s ^ 1])
	{
		cout << 0;
		exit(0);
	}
	//cout << v << ' ' << s << endl;
	while (true)
	{
		pair <int, int> tmp = root[s]->get(v + 1, u[v]);
		if (tmp.first < a[v].second)
		{
			break;
		}
		root[s]->update(tmp.second);
		//cout << v << "-->" << tmp.second << endl;
		dfs(tmp.second, s ^ 1);
	}
	while (true)
	{
		int tmp = -root[2 + s]->get(a[v].first, a[v].second).first;

		//cout << v << " founr " << tmp << endl;

		if (tmp == 0 or tmp > v)
		{
			break;
		}
		root[2 + s]->update(a[tmp].second, -mod);
		//cout << v << "-->" << tmp << endl;
		dfs(tmp, s ^ 1);
	}
	return ;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	for (int i = 1;i <= 2 * n;i++)
	{
		x[i] = -mod;
	}

	for (int i = 1;i <= n;i++)
	{
		cin >> a[i].first >> a[i].second;
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1;i <= n;i++)
	{
		u[i] = lower_bound(a + 1, a + 1 + n, make_pair(a[i].second, 0)) - a;
		x[a[i].second] = -i;
	}


	root[0] = new Node(1, n + 1);
	root[1] = new Node(1, n + 1);
	root[0]->init();
	root[1]->init();

	root[2] = new Node(1, 2 * n + 1);
	root[3] = new Node(1, 2 * n + 1);
	root[2]->init2();
	root[3]->init2();

	int ans = 1;

	for (int i = 1;i <= n;i++)
	{
		if (mark[i][0] or mark[i][1])
		{
			continue;
		}
		ans = ans * 2 % mod;
		dfs(i, 0);
	}
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...