제출 #107322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107322		popovicirobert	Port Facility (JOI17_port_facility)	C++14	0 / 100	3 ms	384 KiB

port_facility

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

struct Node {
    int mx, id;
};


struct SegTree {

    vector <Node> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1, {-INF, -INF});
    }

    inline Node combine(Node &a, Node b) {
        return (a.mx > b.mx) ? a : b;
    }

    void update(int nod, int left, int right, int pos, Node &cur) {
        if(left == right) {
            aint[nod] = cur;
        }
        else {
            int mid = (left + right) / 2;

            if(pos <= mid) update(2 * nod, left, mid, pos, cur);
            else update(2 * nod + 1, mid + 1, right, pos, cur);

            aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
        }
    }

    Node query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod];
        }
        else {
            int mid = (left + right) / 2;
            Node ans = {-INF, -INF};

            if(l <= mid) ans = combine(ans, query(2 * nod, left, mid, l, r));

            if(mid < r) ans = combine(ans, query(2 * nod + 1, mid + 1, right, l, r));

            return ans;
        }
    }

    void update(int pos, Node cur) {
        update(1, 1, n, pos, cur);
    }

    Node query(int l, int r) {
        return query(1, 1, n, l, r);
    }

};


SegTree stl, str;

vector < pair <int, int> > arr;
vector <int> col, vis;
int n;

void dfs(int nod, int c) {

    col[nod] = c;
    vis[nod] = 1;

    while(str.query(arr[nod].first, arr[nod].second).mx > arr[nod].second) {

        auto cur = str.query(arr[nod].first, arr[nod].second);
        Node aux = {-INF, -INF};
        str.update(arr[cur.id].first, aux);

        if(vis[cur.id] == 0) {
             dfs(cur.id, c ^ 1);
        }

    }

    while(-stl.query(arr[nod].first, arr[nod].second).mx < arr[nod].first) {

        auto cur = stl.query(arr[nod].first, arr[nod].second);
        Node aux = {-INF, -INF};
        stl.update(arr[cur.id].second, aux);

        if(vis[cur.id] == 0) {
             dfs(cur.id, c ^ 1);
        }

    }

}

struct Fenwick {

    vector <int> aib;
    int n;

    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }

    inline void update(int pos) {
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i]++;
        }
    }

    inline int query(int pos) {
        int ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }

    inline int sum(int l, int r) {
        return query(r) - query(l - 1);
    }

};


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    arr.resize(n + 1);
    stl.init(2 * n), str.init(2 * n);

    for(i = 1; i <= n; i++) {
        cin >> arr[i].first >> arr[i].second;
        str.update(arr[i].first, {arr[i].second, i});
        stl.update(arr[i].second, {-arr[i].first, i});
    }

    vis.resize(n + 1), col.resize(n + 1);
    int ans = 1;

    for(i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            dfs(i, 0);
            ans *= 2;
            mod(ans);
        }
    }


    Fenwick fen[2];

    for(i = 0; i < 2; i++) {
        fen[i].init(2 * n);
    }

    vector <int> ord(n + 1);
    iota(ord.begin(), ord.end(), 0);

    sort(ord.begin(), ord.end(), [&](const int &a, const int &b) {

            return arr[a].first < arr[b].first;

         });

    for(i = 1; i <= n; i++) {

        if(fen[col[ord[i]]].sum(arr[ord[i]].first, arr[ord[i]].second) > 0) {
            ans = 0;
        }

        fen[col[i]].update(arr[ord[i]].second);

    }


    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

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