Submission #1049181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049181		parsadox2	Port Facility (JOI17_port_facility)	C++17	0 / 100	13 ms	98908 KiB

port_facility

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 2e6 + 10 , mod = 1e9 + 7;
int n , R[N];
pair <int , int> a[N];
set <pair<int , int>> st;

struct DSU{
	set <int> st[N];
	int root[N];
	void Build()
	{
		for(int i = 0 ; i < n ; i++)
		{
			st[a[i].F].insert(a[i].S);
			root[a[i].S] = a[i].F;
		}
	}
	void Merge(int a , int b)
	{
		//cout << a << " MErge " << b << endl;
		n--;
		if(st[a].size() > st[b].size())
			swap(a , b);
		for(auto u : st[a])
		{
			st[b].insert(u);
			root[u] = b;
		}
	}
}dsu;

bool Check_Bipartite()
{
	bool res = true;
	vector <int> A , B;
	A.push_back(mod);
	B.push_back(mod);
	for(int i = 1 ; i <= 2 * n ; i++)
	{
		if(R[i] == 0)
		{
			if(A.back() == i)
				A.pop_back();
			else if(B.back() == i)
				B.pop_back();
			else
				res = false;
		}
		else
		{
			if(A.back() < R[i] || (B.back() < A.back() && B.back() > R[i]))
				B.push_back(R[i]);
			else
				A.push_back(R[i]);
		}
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n;
	int fn = n;
	for(int i = 0 ; i < n ; i++)
		cin >> a[i].F >> a[i].S;
	for(int i = 0 ; i < n ; i++)
	{
		//cout << a[i].F << " " << a[i].S << endl;
		R[a[i].F] = a[i].S;
	}
	if(!Check_Bipartite())
	{
		cout << 0 << '\n';
		return 0;
	}
	dsu.Build();
	for(int i = 1 ; i <= 2 * fn ; i++)
	{
		/*cout << i << " WTF " << endl;
		for(auto u : st)
			cout << u.F << " " << u.S << endl;*/
		if(R[i] == 0)
		{
			auto now = *st.begin();  
			assert(now.F == i);
			st.erase(now);
			dsu.st[now.S].erase(now.F);
			if(!dsu.st[now.S].empty())
				st.insert({*dsu.st[now.S].begin() , now.S});
		}
		else
		{
			//cout << i << " " << R[i] << endl;
			while(!st.empty() && (*st.begin()).F < R[i])
			{
				dsu.Merge(dsu.root[R[i]] , (*st.begin()).S);
				st.erase(st.begin());
			}
			st.insert(make_pair(*dsu.st[dsu.root[R[i]]].begin() , dsu.root[R[i]]));
		}
	}
	int ans = 1;
	for(int i = 0 ; i < n ; i++)
		ans = (ans + ans) % mod;
	cout << ans << '\n';
	return 0;
}

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