Submission #98788

#	Time	Username	Problem	Language	Result	Execution time	Memory
98788		luciocf	Port Facility (JOI17_port_facility)	C++14	0 / 100	2 ms	384 KiB

port_facility

#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";
}

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