Submission #162943

#	Time	Username	Problem	Language	Result	Execution time	Memory
162943		combi1k1	Port Facility (JOI17_port_facility)	C++14	100 / 100	1878 ms	85704 KiB

port_facility

#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);
                if (lead(it1 -> second) == lead(prev(it2) -> second))
                    break;
            }

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

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