Submission #474465

#	Time	Username	Problem	Language	Result	Execution time	Memory
474465		Killer2501	Port Facility (JOI17_port_facility)	C++14	100 / 100	1765 ms	156036 KiB

port_facility

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 2e6+5;
const ll mod = 1e9 + 7;
const int base = 40;
ll n, m, k, t, a[N], b[N], tong, dp[N], lab[N], ans;
char c;
vector<ll> adj[N], kq;
pll p[N];
ll pw(ll k, ll n)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n & 1)total = total * k % mod;
		k = k * k % mod;
	}
	return total;
}

ll findp(ll u)
{
	return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(ll u, ll v)
{
	if(lab[u] > lab[v])swap(u, v);
	lab[u] += lab[v];
	lab[v] = u;

}

void sol()
{
	cin >> n;
	fill_n(lab, n*2+4, -1);
	for(int i = 1; i <= n; i ++)
	{
		cin >> p[i].fi >> p[i].se;
	}
	sort(p+1, p+1+n);
	set<pll> st;
	for(int i = 1; i <= n; i ++)
	{
		auto l = st.lower_bound({p[i].fi, 0ll}), r = st.upper_bound({p[i].se, n*2+1});
		if(l != st.end() && r != st.begin() && (*l).fi < p[i].se)
		{
			r = prev(r);
			while(true)
			{
				pll x = *l;
                ll u = findp(i), v = findp(x.se+n);
                if(u != v)hop(u, v);
                u = findp(i+n), v = findp(x.se);
                if(u != v)hop(u, v);
                if(findp(x.se) == findp((*r).se))break;
                ++l;
			}
		}
		st.insert({p[i].se, i});
	}
	for(int i = 1; i <= n*2; i ++)
	{
		if(i <= n && findp(i) == findp(i+n))
		{
			cout << 0;
			return;
		}
		if(lab[i] < 0)++ans;
	}
	cout << pw(2, ans/2);
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int test = 1;
    //cin >> test;
    while (test-- > 0)
        sol();
    return 0;
}

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