Submission #531780

#	Time	Username	Problem	Language	Result	Execution time	Memory
531780		K4YAN	Port Facility (JOI17_port_facility)	C++17	10 / 100	5 ms	620 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;
ll n, m, q, w;
vector<ll> 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 {
    ll mn, mx, type;
};

struct segtree {

    ll sz = 1;
    item NE = {mxn, -1, -1};
    vector<item> v;


    void init(int n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, NE);
    }
    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);
        return;
    }
    void add_to_mn(int i, pll 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, pll p) {
        add_to_mn(i, p, 0, 0, sz);
        return;
    }
    void add_to_mx(int i, pll 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, pll p) {
        add_to_mx(i, p, 0, 0, sz);
        return;
    }
    pll 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};
        }
        pll 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;
    }
    pll find_mn(int l, int r) {
        return find_mn(l, r, 0, 0, sz);
    }
    pll 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};
        }
        pll 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;
    }
    pll 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<ll> bfs; bfs.push_back(i);
    ll 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;
}

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++) {
        pll p, b;
        p = st.find_mn(A[i] + 1, B[i]);
        b = st.find_mx(A[i] + 1, B[i]);
        if(p.first == mxn || b.first == -1) continue;
        if(p.second == -1 || b.second == -1) continue;
        if(B[p.second] > A[b.second]) {
            cout << "0\n";
            return;
        }
    }
    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: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22