Submission #532135

#	Time	Username	Problem	Language	Result	Execution time	Memory
532135		K4YAN	Port Facility (JOI17_port_facility)	C++17	100 / 100	5846 ms	117172 KiB

port_facility

//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const ll mxn = 2e6 + 16, md = 1e9 + 7;//9:55
int n, m, q, w;
int clr[mxn];
vector<int> A, B;
bitset<mxn> mark;

void input() {

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> q; q--; 
        A.push_back(q);
        cin >> q; q--;
        B.push_back(q);
    }

}

struct item {
    int mn, mx, type;
};
struct item2 {
    int n0, n1;
};

struct segtree {

    int sz = 1;
    item NE = {mxn, -1, -1};
    item2 NE2 = {mxn, mxn};
    vector<item> v;
    vector<item2> osc;

    void init(int n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, NE);
        osc.assign(2 * sz, NE2);
    }
    void update(int x) {
        v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn);
        v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx);
        osc[x].n0 = min(osc[2 * x + 1].n0, osc[2 * x + 2].n0);
        osc[x].n1 = min(osc[2 * x + 1].n1, osc[2 * x + 2].n1);
        return;
    }
    void add(int i, pii p, int x, int lx, int rx) {
        if(rx - lx == 1) {
            if(p.second == 0) osc[x].n0 = p.first;
            else osc[x].n1 = p.first;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) add(i, p, 2 * x + 1, lx, m);
        else add(i, p, 2 * x + 2, m, rx);
        update(x);
    }
    void add(int i, pii p) {
        add(i, p, 0, 0, sz);
        return;
    }
    int SAGZAN(int l, int r, int typ, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return mxn;
        if(l <= lx && rx <= r) {
            if(typ == 0) return osc[x].n0;
            return osc[x].n1;
        }
        int m = (lx + rx) >> 1;
        int ans = SAGZAN(l, r, typ, 2 * x + 1, lx, m);
        ans = min(ans, SAGZAN(l, r, typ, 2 * x + 2, m, rx));
        return ans;
    }
    int SAGZAN(int l, int r, int typ) {
        return SAGZAN(l, r, typ, 0, 0, sz);
    }
    void add_to_mn(int i, pii p, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x].mn = p.first, v[x].type = p.second;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) add_to_mn(i, p, 2 * x + 1, lx, m);
        else add_to_mn(i, p, 2 * x + 2, m, rx);
        v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn);
        return;
    }
    void add_to_mn(int i, pii p) {
        add_to_mn(i, p, 0, 0, sz);
        return;
    }
    void add_to_mx(int i, pii p, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x].mx = p.first, v[x].type = p.second;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) add_to_mx(i, p, 2 * x + 1, lx, m);
        else add_to_mx(i, p, 2 * x + 2, m, rx);
        v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx);
        return;
    }
    void add_to_mx(int i, pii p) {
        add_to_mx(i, p, 0, 0, sz);
        return;
    }
    pii find_mn(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return {mxn, -1};
        if(rx - lx == 1) {
            if(v[x].mn < l - 1) {
                return {v[x].mn, v[x].type};
            } return {mxn, -1};
        }
        int m = (lx + rx) >> 1;
        if(l <= lx && rx <= r) {
            if(v[2 * x + 2].mn < l - 1) {
                return find_mn(l, r, 2 * x + 2, m, rx);
            } if(v[2 * x + 1].mn < l - 1) {
                return find_mn(l, r, 2 * x + 1, lx, m);
            } return {mxn, -1};
        }
        pii p = find_mn(l, r, 2 * x + 2, m, rx);
        if(p.first < mxn) return p;
        p = find_mn(l, r, 2 * x + 1, lx, m);
        return p;
    }
    pii find_mn(int l, int r) {
        return find_mn(l, r, 0, 0, sz);
    }
    pii find_mx(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return {-1, -1};
        if(rx - lx == 1) {
            if(v[x].mx > r) {
                return {v[x].mx, v[x].type};
            } return {-1, -1};
        }
        int m = (lx + rx) >> 1;
        if(l <= lx && rx <= r) {
            if(v[2 * x + 1].mx > r) {
                return find_mx(l, r, 2 * x + 1, lx, m);
            } if(v[2 * x + 2].mx > r) {
                return find_mx(l, r, 2 * x + 2, m, rx);
            } return {-1, -1};
        }
        pii p = find_mx(l, r, 2 * x + 1, lx, m);
        if(p.first > -1) return p;
        p = find_mx(l, r, 2 * x + 2, m, rx);
        return p;
    }
    pii find_mx(int l, int r) {
        return find_mx(l, r, 0, 0, sz);
    }
    void set(int i, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] = NE;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) set(i, 2 * x + 1, lx, m);
        else set(i, 2 * x + 2, m, rx);
        update(x); return;
    }
    void set(int i) {
        set(i, 0, 0, sz);
        return;
    }

}; segtree st;

inline void BFS(int i) {
    vector<int> bfs; bfs.push_back(i);
    int ptr = 0, x; pll p;
    st.set(A[i]), st.set(B[i]);

    while(ptr < int(bfs.size())) {
        x = bfs[ptr++];
        mark.set(x);
        p = {0, 0};
        while(p.second > -1) {
            p = st.find_mx(A[x] + 1, B[x]);
            if(p.second == -1 || p.first == -1) break;
            bfs.push_back(p.second); 
            st.set(A[p.second]), st.set(B[p.second]);
        } p = {0, 0};
        while(p.second > -1) {
            p = st.find_mn(A[x] + 1, B[x]);
            if(p.second == -1 || p.first == mxn) break;
            bfs.push_back(p.second);
            st.set(A[p.second]), st.set(B[p.second]);
        }
    }
    return;
}
inline void BFS_0(int i) {
    vector<int> bfs; bfs.push_back(i);
    int ptr = 0, x; pll p;
    st.set(A[i]), st.set(B[i]);

    while(ptr < int(bfs.size())) {
        x = bfs[ptr++];
        mark.set(x);
        p = {0, 0};
        while(p.second > -1) {
            p = st.find_mx(A[x] + 1, B[x]);
            if(p.second == -1 || p.first == -1) break;
            bfs.push_back(p.second); clr[p.second] = clr[x] ^ 1;
            st.set(A[p.second]), st.set(B[p.second]);
        } p = {0, 0};
        while(p.second > -1) {
            p = st.find_mn(A[x] + 1, B[x]);
            if(p.second == -1 || p.first == mxn) break;
            bfs.push_back(p.second); clr[p.second] = clr[x] ^ 1;
            st.set(A[p.second]), st.set(B[p.second]);
        }
    }
    return;
}

void solve() {

    st.init(2 * n);
    for(int i = 0; i < n; i++) {
        st.add_to_mn(B[i], {A[i], i});
        st.add_to_mx(A[i], {B[i], i});
    }
    for(int i = 0; i < n; i++) {
        if(!mark[i]) {
            BFS_0(i);
        }
    } mark.reset();
    for(int i = 0; i < n; i++) {
        st.add(B[i], {A[i], clr[i]});
    }
    for(int i = 0; i < n; i++) {
        q = st.SAGZAN(A[i] + 1, B[i], clr[i]);
        if(q < A[i]) {
            cout << "0\n";
            return;
        }
    }
    for(int i = 0; i < n; i++) {
        st.add_to_mn(B[i], {A[i], i});
        st.add_to_mx(A[i], {B[i], i});
    }
    ll cnt = 0, ans = 1;
    for(int i = 0; i < n; i++) {
        if(!mark[i]) {
            BFS(i); cnt++;
        }
    }
    for(int i = 0; i < cnt; i++) {
        ans <<= 1; ans %= md;
    } cout << ans << endl;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();  

    return 0;

}

Compilation message (stderr)

port_facility.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("Ofast,unroll-loops")
      |

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