Submission #107330

#	Time	Username	Problem	Language	Result	Execution time	Memory
107330		popovicirobert	Port Facility (JOI17_port_facility)	C++14	78 / 100	6002 ms	246016 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 SegTree {

    vector <int> aint;
    int n;

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

    void update(int nod, int left, int right, int pos, int 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] = max(aint[2 * nod], aint[2 * nod + 1]);
        }
    }

    int 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;
            int ans = -INF;

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

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

            return ans;
        }
    }

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

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

};


SegTree stl, str;

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

void dfs(int nod, int c) {

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

    while(1) {

        int cur = str.query(arr[nod].first, arr[nod].second);

        if(cur <= arr[nod].second) {
            break;
        }

        int id = who[cur];

        str.update(arr[id].first, -INF);

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

    }

    while(1) {

        int cur = -stl.query(arr[nod].first, arr[nod].second);

        if(cur >= arr[nod].first) {
            break;
        }

        int id = who[cur];

        stl.update(arr[id].second, -INF);

        if(vis[id] == 0) {
             dfs(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);
    who.resize(2 * n + 1);

    for(i = 1; i <= n; i++) {
        cin >> arr[i].first >> arr[i].second;

        str.update(arr[i].first, arr[i].second);
        stl.update(arr[i].second, -arr[i].first);

        who[arr[i].first] = who[arr[i].second] = 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++) {

        int id = ord[i];

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

        fen[col[id]].update(arr[id].second);

    }


    cout << ans;

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

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