Submission #471449

#TimeUsernameProblemLanguageResultExecution timeMemory
471449RainbowbunnyPort Facility (JOI17_port_facility)C++17
100 / 100
1038 ms83396 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
const int mod = 1e9 + 7;

int n, ans = 1;
int dsu[2 * MAXN];
pair <int, int> A[MAXN];
map <int, int> M;

int Root(int node)
{
    return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}

void Union(int x, int y)
{
    x = Root(x);
    y = Root(y);
    if(x == y)
    {
        return;
    }
    dsu[x] = y;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> A[i].first >> A[i].second;
        dsu[i] = i;
        dsu[i + n] = i + n;
    }
    sort(A + 1, A + n + 1);
    for(int i = 1; i <= n; i++)
    {
        map <int, int> :: iterator it1 = M.lower_bound(A[i].first);
        map <int, int> :: iterator it2 = M.lower_bound(A[i].second);
        while(it1 != it2)
        {
            Union(i, it1->second + n);
            Union(i + n, it1->second);
            if(Root(i) == Root(i + n))
            {
                cout << 0 << '\n';
                return 0;
            }
            if(Root(it1->second) == Root(it1->second + n))
            {
                cout << 0 << '\n';
                return 0;
            }
            int id = prev(it2)->second;
            if(Root(id) == Root(it1->second))
            {
                break;
            }
            it1++;
        }
        M[A[i].second] = i;
    }
    for(int i = 1; i <= n; i++)
    {
        if(Root(i) == i)
        {
            ans = ans * 2 % mod;
        }
    }
    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...