제출 #1046335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046335		earlyamazon	Port Facility (JOI17_port_facility)	C++14	78 / 100	2204 ms	1048576 KiB

port_facility

// n <= 2000

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int mn = 2e6+7;
int n;
vector<pair<int,int>> t;
bool dwu = 1;
set<pair<int,int>> d[mn*2]; //{L, ind przedzialu}
int rep[mn], waga[mn];
int odw[mn];
vector<int> G[mn];

bool krawedz(pair<int,int> a, pair<int,int> b){
    swap(a.first, a.second);
    swap(b.first, b.second);
    return (a.first < b.first && b.first < a.second) ^ (a.first < b.second && b.second < a.second);
}

int findd(int a){
    if (rep[a] == a) return a;
    return rep[a] = findd(rep[a]);
}

void unionn(int x, int y){
    int a = findd(x);
    int b = findd(y);
    if (a == b) return;
    if (waga[a] < waga[b]) swap(a,b);
    rep[b] = a;
    waga[a] += waga[b];
    G[x].push_back(y);
    G[y].push_back(x);
}

void mergenode(int poz, pair<int,int> x){
    if (d[poz].empty()) return;
    pair<int,int> naj = *d[poz].begin();
    while (!d[poz].empty() && *d[poz].begin() < x){
        // cout<<"xd "<<x.second<<" "<<(*d[poz].begin()).second<<"\n";
        unionn(x.second, (*d[poz].begin()).second);
        d[poz].erase(d[poz].begin());
    }
    d[poz].insert(naj);
}

void update(int ind, pair<int,int> x){
    ind += mn;
    d[ind].insert(x);
    while (ind /= 2) d[ind].insert(x);
}

void mergee(int l, int r, pair<int,int> x){
    for (l += mn, r += mn+1; l < r; l /= 2, r /= 2){
        if (l&1) mergenode(l++, x);
        if (r&1) mergenode(--r, x);
    }
}

void dfs(int v, int kt){
    // cout<<v<<" ";
    // teraz.push_back(v);
    odw[v] = kt;
    for (auto i : G[v]){
        if (!odw[i]){
            if (kt == 1) dfs(i, 2);
            else dfs(i, 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cout.tie(0);
    cin>>n;
    for (int i = 0; i < n; i++){
        int a,b;
        cin>>a>>b;
        t.push_back({b,a});
        rep[i] = i;
        waga[i] = 1;
    }
    sort(t.begin(), t.end());
    for (int i = 0; i < n; i++){
        int L = t[i].second;
        int R = t[i].first;
        mergee(L, R, {L, i});
        update(R, {L, i});
    }
    int ile = 0;
    for (int i = 0; i < n; i++){
        if (!odw[i]){
            dfs(i, 1);
            ile++;
            // cout<<"\n";
            // cout<<"\n";
        }
    }
    vector<pair<pair<int,int>, int>> t2;
    for (int i = 0; i < n; i++){
        t2.push_back({{t[i].second, t[i].first}, i});
    }
    t.push_back({3*n, 3*n});
    sort(t2.begin(), t2.end());
    rep[n] = n;
    vector<pair<int,int>> st1 = {{2*n+1, n}}, st2 = {{2*n+1, n}};
    for (int i = 0; i < n; i++){
        int L = t2[i].first.first;
        int R = t2[i].first.second;
        int poz = t2[i].second;
        // cout<<L<<" "<<R<<" "<<poz<<"\n";

        while (st1.back().first < L) st1.pop_back();
        while (st2.back().first < L) st2.pop_back();

        int poz1 = st1.back().second;
        // int R1 = st1.back().first;
        int poz2 = st2.back().second;
        // int R2 = st2.back().first;

        if ((findd(poz) == findd(poz1) && odw[poz] == odw[poz1]) || (findd(poz) == findd(poz2) && odw[poz] != odw[poz2])){
            if (krawedz(t[poz], t[poz1])){
                dwu = 0;
                break;
            }
            st1.push_back({R, poz});
            // cout<<'a';
        }
        else if ((findd(poz) == findd(poz1) && odw[poz] != odw[poz1]) || (findd(poz) == findd(poz2) && odw[poz] == odw[poz2])){
            if (krawedz(t[poz], t[poz2])){
                dwu = 0;
                break;
            }
            st2.push_back({R, poz});
            // cout<<'b';
        }
        else if (findd(poz) != findd(poz1) && findd(poz) != findd(poz2)){
            st1.push_back({R, poz});
            // cout<<'c';
        }
        else{
            assert(0);
        }
    }
    int w = 1;
    if (!dwu) w = 0;
    for (int i = 0; i < ile; i++) w = (w*2)%mod;
    cout<<w<<"\n";

}

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