제출 #1198482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198482		JooDdae	Port Facility (JOI17_port_facility)	C++20	10 / 100	1 ms	328 KiB

port_facility

#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);
            int c = 0;
            while(it != mp.end()) {
                if(merge(u, it->second)) return cout << 0, 0;
                it++;
                if(++c >= 50) break;
            }
        }
    }

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

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