Submission #1297998

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

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

pair <int, int> a[maxn];
int u[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;
	}

	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 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 {0, 0};
		}
		if (l == L and R == r)
		{
			return v;
		}
		pair <int, int> ret = {0, 0};
		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[2];

void dfs(int v, bool s)
{
//	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);
	}
	return ;
}

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

	int n;
	cin >> n;
	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;
	}

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

	int ans = 1;

	for (int i = 1;i <= n;i++)
	{
		int m1 = root[0]->get(i, i + 1).first, m2 = root[1]->get(i, i + 1).first;
		if (m1 == 0 and m2 == 0)
		{
			cout << 0;
			return 0;
		}
		if (m1 == 0 or m2 == 0)
		{
			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...