제출 #529235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529235		K4YAN	Port Facility (JOI17_port_facility)	C++17	10 / 100	5 ms	600 KiB

port_facility

//Be Name Khoda

#include<bits/stdc++.h>

using namespace std;

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

const ll mxn = 1e6 + 16, md = 1e9 + 7;
ll n, m, q;
ll c[2 * mxn], t[2 * mxn];
bool ok[2 * mxn];
vector<ll> a, b;

struct item {
    ll mn, mx;
};
struct segtree {

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

    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, NE);
        b.assign(2 * sz, 1);
    }
    void set_A(int i, ll q, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x].mn = q;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) set_A(i, q, 2 * x + 1, lx, m);
        else set_A(i, q, 2 * x + 2, m, rx);
        v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn);
        return;
    }
    void set_A(int i, ll q) {
        set_A(i, q, 0, 0, sz);
        return;
    }
    void set_B(int i, ll q, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x].mx = q;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) set_B(i, q, 2 * x + 1, lx, m);
        else set_B(i, q, 2 * x + 2, m, rx);
        v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx);
        return;
    }
    void set_B(int i, ll q) {
        set_B(i, q, 0, 0, sz);
        return;
    }
    void set(int i, int x, int lx, int rx) {
        if(rx - lx == 1) {
            b[x] = 0;
            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);
        v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx);
        v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn);
        b[x] = b[2 * x + 1] | b[2 * x + 2];
        return;
    }
    void set(int i) {
        set(i, 0, 0, sz);
        return;
    }
    pii cal(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return {2 * mxn, -1};
        if(l <= lx && rx <= r) {
            return make_pair(v[x].mn, v[x].mx);
        }
        int m = (lx + rx) >> 1;
        pii ans = cal(l, r, 2 * x + 1, lx, m);
        pii ans2 = cal(l, r, 2 * x + 2, m, rx);
        ans.first = min(ans.first, ans2.first);
        ans.second = max(ans.second, ans2.second);
        return ans;
    }
    pii cal(int l, int r) {
        return cal(l, r, 0, 0, sz);
    }
    pii find_mn(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return {2 * mxn, 2 * mxn};
        if(rx - lx == 1) {
            if(!b[x]) return {2 * mxn, 2 * mxn};
            if(v[x].mn < l - 1) return {v[x].mn, lx};
            return {2 * mxn, 2 * mxn};
        }
        if(l <= lx && rx <= r) {
            if(v[x].mn >= l - 1) return {2 * mxn, 2 * mxn};
            if(!b[x]) return {2 * mxn, 2 * mxn};
            int m = (lx + rx) >> 1;
            if(v[2 * x + 2].mn < l - 1) return find_mn(l, r, 2 * x + 2, m, rx);
            return find_mn(l, r, 2 * x + 1, lx, m);
        }
        int m = (lx + rx) >> 1;
        pii ans = find_mn(l, r, 2 * x + 2, m, rx);
        if(ans.second == 2 * mxn) {
            ans = find_mn(l, r, 2 * x + 1, lx, m);
        }
        return ans;
    }
    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 {2 * mxn, 2 * mxn};
        if(rx - lx == 1) {
            if(!b[x]) return {2 * mxn, 2 * mxn};
            if(v[x].mx > r) return {v[x].mx, lx};
            return {2 * mxn, 2 * mxn};
        }
        if(l <= lx && rx <= r) {
            if(v[x].mx <= r) return {2 * mxn, 2 * mxn};
            if(!b[x]) return {2 * mxn, 2 * mxn};
            int m = (lx + rx) >> 1;
            if(v[2 * x + 1].mx > r) return find_mx(l, r, 2 * x + 1, lx, m);
            return find_mx(l, r, 2 * x + 2, m, rx);
        }
        int m = (lx + rx) >> 1;
        pii ans = find_mx(l, r, 2 * x + 1, lx, m);
        if(ans.second == 2 * mxn) {
            ans = find_mx(l, r, 2 * x + 2, m, rx);
        }
        return ans;
    }
    pii find_mx(int l, int r) {
        return find_mx(l, r, 0, 0, sz);
    }

}; segtree st;
bitset<2 * mxn> mark;
pll p, d;

inline void input() {

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> q; q--;
        a.push_back(q); ok[q] = 1; c[q] = i;
        cin >> q; q--;
        b.push_back(q); t[a.back()] = q; c[q] = i;
    }

}

inline void BFS(int i) {

    vector<ll> bfs;
    bfs.push_back(i);
    st.set(a[i]); st.set(b[i]);
    ll ptr = 0;
    while(ptr < int(bfs.size())) {
        auto u = bfs[ptr++];
        mark.set(a[u]), mark.set(b[u]);
        p = {0, 0};
        while(p.second != 2 * mxn) {
            p = st.find_mx(a[u] + 1, b[u]);
            if(p.second == 2 * mxn) break;
            bfs.push_back(c[p.second]);
            st.set(a[c[p.second]]); st.set(b[c[p.second]]);
        } p = {0, 0};
        while(p.second != 2 * mxn) {
            p = st.find_mn(a[u] + 1, b[u]);
            if(p.second == 2 * mxn) break;
            bfs.push_back(c[p.second]);
            st.set(a[c[p.second]]); st.set(b[c[p.second]]);
        }
    }

}

inline void solve() {

    st.init(2 * n);
    for(int i = 0; i < n; i++) {
        st.set_A(b[i], a[i]);
        st.set_B(a[i], b[i]);
    }
    for(int i = 0; i < n; i++) {
        p = st.find_mn(a[i] + 1, b[i]);
        d = st.find_mx(a[i] + 1, b[i]);
        if(d.second == 2 * mxn || p.second == 2 * mxn) continue;
        if(p.second > d.second && p.first < a[i] && d.first > b[i]) {
            cout << "0\n";
            return;
        }
    }
    ll ans = 1;
    for(int i = 0; i < n; i++) {
        p = st.cal(a[i] + 1, b[i]);
        if(p.first == 2 * mxn) p.first = a[i];
        if(p.second == -1) p.second = b[i];
        if(a[i] <= p.first && p.second <= b[i]) {
            ans *= 2;
            ans %= md;
            mark.set(a[i]);
            mark.set(b[i]);
        }
    } 
    for(int i = 0; i < 2 * n; i++) {
        if(mark[i]) st.set(i);
    } 
    for(int i = 0; i < n; i++) {
        if(mark[a[i]]) continue;
        BFS(i);
        ans *= 2;
        ans %= md;
    }
    cout << ans << endl;
    return;

}

int main() {

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

    input(), solve();

    return 0; 

}

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