Submission #162940

#TimeUsernameProblemLanguageResultExecution timeMemory
162940combi1k1Port Facility (JOI17_port_facility)C++14
22 / 100
6090 ms8816 KiB
#include<bits/stdc++.h>

using namespace std;

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 2e6 + 1;

typedef pair<int,int>   ii;

int p[N];
int s[N];

int lead(int x) {
    return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y)   {
    x = lead(x);
    y = lead(y);
    if (x == y) return  0;
    if (s[x] < s[y])
        swap(x,y);
    p[y] = x;
    s[x] += s[y];

    return  1;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    vector<ii>  vec;

    FOR(i,0,n)  {
        int x;  cin >> x;
        int y;  cin >> y;

        vec.push_back(ii(x,y));

        p[i] = i;   p[i + n] = i + n;
        s[i] = 1;   s[i + n] = 1;
    }

    sort(vec.begin(),vec.end());

    map<int,int> mp;

    FOR(i,0,n)  {
        auto it1 = mp.lower_bound(vec[i].first);
        auto it2 = mp.upper_bound(vec[i].second);

        if (it2 != mp.begin())
            for(; it1 != it2 ; ++it1)   {
                join(i,n + it1 -> second);
                join(i + n,it1 -> second);
            }

        mp[vec[i].second] = i;
    }
    int ans = 1;

    FOR(i,0,n)  {
        if (lead(i) == lead(i + n)) ans = 0;
        if (lead(i) == i)
            ans *= 2,
            ans %= 1000000007;
    }

    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...