제출 #1047214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047214		earlyamazon	Port Facility (JOI17_port_facility)	C++14	100 / 100	1634 ms	463236 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;
vector<pair<int,int>> d[mn*2]; //{L, ind przedzialu}
pair<int,int> pier[mn*2];
int start[mn*2];
int rep[mn], waga[mn];
int odw[mn];
vector<int> G[mn];

bool krawedz(pair<int,int> a, pair<int,int> b){
    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 (pier[poz] == make_pair(-1, -1)) return;
    // pair<int,int> naj = d[poz].front();
    if (pier[poz] < x) unionn(x.second, pier[poz].second);
    while (start[poz] < (int)d[poz].size() && d[poz][start[poz]] < x){
        // cout<<"xd "<<x.second<<" "<<(*d[poz].begin()).second<<"\n";
        unionn(x.second, (d[poz][start[poz]]).second);
        // d[poz].erase(d[poz].begin());
        start[poz]++;
    }
    // d[poz].push_front(naj);
}

void update(int ind, pair<int,int> x){
    ind += mn;
    if (pier[ind] == make_pair(-1,-1)) pier[ind] = x;
    else d[ind].push_back(x);
    while (ind /= 2){
        if (pier[ind] == make_pair(-1,-1)) pier[ind] = x;
        else d[ind].push_back(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);
    for (int i = 0; i < 2*mn; i++){
        pier[i] = {-1, -1};
    }
    cin>>n;
    for (int i = 0; i < n; i++){
        int a,b;
        cin>>a>>b;
        t.push_back({a,b});
        rep[i] = i;
        waga[i] = 1;
    }
    sort(t.begin(), t.end());
    for (int i = 0; i < n; i++){
        int L = t[i].first;
        int R = t[i].second;
        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";
        }
    }
    t.push_back({3*n, 3*n});
    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 = t[i].first;
        int R = t[i].second;
        int poz = i;
        // 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: 22 / 22