Submission #1098042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098042		orcslop	Wall (IOI14_wall)	C++17	100 / 100	671 ms	151752 KiB

wall

#include <bits/stdc++.h>
using namespace std;
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int inf = 1e9; 

struct Data {
    int mn = 0, mx = inf; 
}; 

/**
 * T = tree node type, which wiint be long long
 * We use the Query struct to manage updates.
 */
template <class T> class LazySegtree {
  private:
    const int sz;
    vector<Data> tree;      // tree[i] = sum of this node's range
    vector<Data> lazy;  // lazy[i] = lazy update for the range

    /** @return result of joining two tree nodes together */

    /** applies lazy update to t[v], places update at lz[v] */
    void apply(int v, const Data &x) {
        ckmax(tree[v].mn, x.mn); 
        ckmax(tree[v].mx, tree[v].mn); 
        ckmin(tree[v].mx, x.mx); 
        ckmin(tree[v].mn, tree[v].mx); 
    }

    /** pushes down lazy update to children of v */
    void push_down(int v) {
        apply(2 * v, tree[v]);
        apply(2 * v + 1, tree[v]);
        tree[v] = Data(); 
    }

    void range_update(int v, int l, int r, int ql, int qr, const Data &x) {
        if (qr < l || ql > r) { return; }
        if (ql <= l && r <= qr) {
            apply(v, x);
        } else {
            push_down(v);
            int m = (l + r) / 2;
            range_update(2 * v, l, m, ql, qr, x);
            range_update(2 * v + 1, m + 1, r, ql, qr, x);
        }
    }

    Data get(int v, int pos, int l, int r) {
        if (l == r) { return tree[v]; }
        push_down(v);
        int m = (l + r) / 2;
        if(pos <= m) return get(2 * v, pos, l, m); 
        else return get(2 * v + 1, pos, m + 1, r); 
    }

  public:
    LazySegtree(int n) : sz(n), tree(4 * sz), lazy(4 * sz) {
        
    }

    /** updates [ql, qr] with the update x */
    void range_update(int ql, int qr, const Data &x) {
        range_update(1, 0, sz - 1, ql, qr, x);
    }

    /** sum of array values on [ql, qr] */
    Data get(int pos) { return get(1, pos, 0, sz - 1); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int final_height[]) {
    LazySegtree<int> st(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            st.range_update(left[i], right[i], {height[i], inf});
        } else {
            st.range_update(left[i], right[i], {0, height[i]});
        }
    }
    for (int i = 0; i < n; i++) { 
        Data c = st.get(i); 
        if(c.mn <= height[i] && height[i] <= c.mx){
            final_height[i] = height[i]; 
        }
        final_height[i] = c.mn; 
    }
}

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