Submission #1198472

#TimeUsernameProblemLanguageResultExecution timeMemory
1198472JooDdaePort Facility (JOI17_port_facility)C++20
22 / 100
6093 ms8520 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

int n, l[1001001], r[1001001], z[2002002], p[2002002];

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
int merge(int x, int y) {
    p[find(x+n)] = find(y);
    p[find(y+n)] = find(x);
    return find(x) == find(y);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> l[i] >> r[i];
        z[l[i]] = i, z[r[i]] = -i;
    }

    map<int, int> mp;
    iota(p+1, p+1+n+n, 1);
    for(int i=1;i<=n+n;i++) {
        if(z[i] > 0) {
            mp[i] = z[i];
        } else {
            int u = -z[i];
            
            auto it = mp.find(l[u]);
            it = mp.erase(it);
            while(it != mp.end()) {
                if(merge(u, it->second)) return cout << 0, 0;
                it++;
            }
        }
    }

    for(int i=1;i<=n;i++) p[find(i+n)] = find(i);

    int ans = 1;
    for(int i=1;i<=n;i++) if(i == find(i)) ans = ans*2%mod;
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...