Submission #1145683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145683		musho	벽 (IOI14_wall)	C++20	61 / 100	624 ms	267784 KiB

wall

    #include <bits/stdc++.h>
    #include <algorithm>
    #include <set>
     
    using namespace std;
     
     
    const int N_MAX = 2000002;
    const int K_MAX = 500002;
    const int V_MAX = 100002;
    const int ST_MAX = (1 << 18) + 2;
     
    set <int> q_ind_up[V_MAX], q_ind_down[V_MAX];
    int st_up[ST_MAX], st_down[ST_MAX];
     
    void build(int v, int s, int e) {
        st_up[v] = st_down[v] = -1;
        if (s == e) {
            return;
        }
        int m = (s + e) / 2;
        build(v*2, s, m);
        build(v*2+1, m+1, e);
    }
     
    void update(int v, int s, int e, int p, int val, bool up) {
        if (s == e){
            if (up) st_up[v] = val;
            else st_down[v] = val;
            return;
        }
     
        int m = (s + e) / 2;
        
        if (p <= m) update(v*2, s, m, p, val, up);
        else update(v*2+1, m+1, e, p, val, up);
     
        if (up) st_up[v] = max(st_up[v*2], st_up[v*2+1]);
        else st_down[v] = max(st_down[v*2], st_down[v*2+1]);
     
    }
     
    int get(int v, int s, int e, int l, int r, bool up) {
        if (l > r) return -1;
        if (s == l && e == r) {
            if (up) return st_up[v];
            return st_down[v];
        }
        int m = (s + e) / 2;
        int lft = get(v*2, s, m, l, min(r, m), up);
        int rgt = get(v*2+1, m+1, e, max(l, m+1), r, up);
        return max(lft, rgt);
    }
     
    int get_set_last(const set<int> &s) {
        int res = -1;
        if (s.size() > 0){
            auto it = s.end();
            --it;
            res = (*it);
        }
        return res;
    }
     
    void add_flag(int height, int q_ind, bool up) {
        set<int> &ind_set = up ? q_ind_up[height] : q_ind_down[height];
        
        int old = get_set_last(ind_set);
        ind_set.insert(q_ind);
        int nw = get_set_last(ind_set);
     
        if (old != nw) {
            update(1, 0, V_MAX-2, height, nw, up);
        }
    }
     
    void remove_flag(int height, int q_ind, bool up) {
        set<int> &ind_set = up ? q_ind_up[height] : q_ind_down[height];
        
        int old = get_set_last(ind_set);
        ind_set.erase(q_ind);
        int nw = get_set_last(ind_set);
     
        if (old != nw) {
            update(1, 0, V_MAX-2, height, nw, up);
        }
    }
     
    bool check_lb(int lb) {
        int down_ind_max = get(1, 0, V_MAX-2, 0, lb-1, false);
        int up_ind_max = get(1, 0, V_MAX-2, lb, V_MAX-2, true);
     
        if (up_ind_max == -1) {
            return false;
        }
     
        if (down_ind_max == -1) {
            return true;
        }
     
        return up_ind_max > down_ind_max;
    }
     
    int find_height() {
        int S = 0, E = V_MAX-2;
        int res = 0;
        while(S <= E) {
            int M = (S+E) / 2;
            if (check_lb(M)) {
                res = M;
                S = M+1;
            }
            else {
                E = M-1;
            }
        }
        return res;
    }
     
    int find_height2(int v, int s, int e, int up_ind_carry, int down_ind_carry) {
        if (s == e) {
            return s;
        }
     
        int m = (s + e) / 2;
     
        int down_ind_max = max(st_down[v*2], down_ind_carry);
        int up_ind_max = max(st_up[v*2+1], up_ind_carry);
     
        if (up_ind_max == -1) {
            return find_height2(v*2, s, m, up_ind_carry, down_ind_carry);
        }
     
        if (down_ind_max == -1) {
            return find_height2(v*2+1, m+1, e, up_ind_carry, down_ind_carry);
        }
     
        if (up_ind_max > down_ind_max) {
            return find_height2(v*2+1, m+1, e, up_ind_carry, max(down_ind_carry, down_ind_max));
        }
        else {
            return find_height2(v*2, s, m, max(up_ind_carry, up_ind_max), down_ind_carry);
        }
     
    }
     
    void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
        build(1, 0, V_MAX-2);
        vector < vector<int> > up_flags(n), down_flags(n);
        vector < vector<int> > up_flags_neg(n), down_flags_neg(n);
     
        for(int i = 0; i < k; ++i) {
            if (op[i] == 1) {
                up_flags[left[i]].push_back(i);
                if (right[i] < n - 1) up_flags_neg[right[i]+1].push_back(i); 
            }
            else {
                down_flags[left[i]].push_back(i);
                if (right[i] < n - 1) down_flags_neg[right[i]+1].push_back(i); 
            }
        }
     
        for (int i = 0; i < n; ++i) {
            // add flags
            for (const auto &q_ind: up_flags[i]) {
                add_flag(height[q_ind], q_ind, true);
            }
            for (const auto &q_ind: down_flags[i]) {
                add_flag(height[q_ind], q_ind, false);
            }
     
            // remove flags
            for (const auto &q_ind: up_flags_neg[i]) {
                remove_flag(height[q_ind], q_ind, true);
            }
            for (const auto &q_ind: down_flags_neg[i]) {
                remove_flag(height[q_ind], q_ind, false);
            }
     
           // finalHeight[i] = find_height();
           finalHeight[i] = find_height2(1, 0, V_MAX-2, -1, -1);
        }
    }

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39