Submission #244404

#	Time	Username	Problem	Language	Result	Execution time	Memory
244404		Osama_Alkhodairy	Port Facility (JOI17_port_facility)	C++17	100 / 100	1498 ms	76724 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 1000001;

int n, p[2 * N], mod = 1e9 + 7;
vector <pair <int, int> > a;

int find(int x){
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}
void merge(int x, int y){
    x = find(x);
    y = find(y);
    p[x] = y;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    for(auto &i : a){
        cin >> i.first >> i.second;
        i.first--; i.second--;
    }
    sort(a.begin(), a.end());
    for(int i = 0 ; i < 2 * n ; i++){
        p[i] = i;
    }
    map <int, int> mp;
    for(int i = 0 ; i < n ; i++){
        auto from = mp.lower_bound(a[i].first), to = mp.upper_bound(a[i].second);
        if(from != to && to != mp.begin()){
            to--;
            while(from != mp.end()){
                merge(i, from->second + n);
                merge(i + n, from->second);
                if(to == from || find(from->second) == find(to->second)) break;
                from++;
            }
        }
        mp[a[i].second] = i;
    }
    int ans = 1;
    for(int i = 0 ; i < n ; i++){
        if(find(i) == find(i + n)){
            finish(0);
        }
        if(find(i) == i){
            ans *= 2;
            if(ans >= mod) ans -= mod;
        }
    }
    cout << ans << endl;
}

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