제출 #98788

#제출 시각아이디문제언어결과실행 시간메모리
98788luciocfPort Facility (JOI17_port_facility)C++14
0 / 100
2 ms384 KiB
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

int a[maxn], b[maxn];

int open[maxn], close[maxn];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i];

		open[a[i]] = i, close[b[i]] = i;
	}

	ll ans = 1LL;
	set<int> S;

	priority_queue<int, vector<int>, greater<int> > fila;
	fila.push(2*n+1); fila.push(2*n+2);

	for (int i = 1; i <= 2*n; i++)
	{
		if (open[i])
		{
			int x = fila.top(); fila.pop();
			int y = fila.top();

			if (b[open[i]] < x && b[open[i]] < y) 
				ans = (ans*2)%mod;
			else if (b[open[i]] > x && b[open[i]] > y)
			{
				ans = 0;
				break;
			}

			fila.push(x); fila.push(b[open[i]]);
		}
		else
		{
			int x = fila.top(); fila.pop();

			if (b[close[i]] == x) continue;
			else fila.pop();

			fila.push(x);
		}
	}

	cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...