IOI '14 P2 - Wall (Standard I/O)

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e6;

struct Segtree {
    int n;
    vector<int> left, right;
    Segtree() {}
    Segtree(int nn) {
        n = nn;
        left = vector<int>(4*n);
        right = vector<int>(4*n, INF);
    }
    void combine(int i, int l, int r) { // add {l, r} onto i
        if (i > left.size()) return;
        if (l > right[i]) left[i] = right[i] = l;
        else if (r < left[i]) left[i] = right[i] = r;
        else left[i] = max(left[i], l), right[i] = min(right[i], r);
    }
    void propagate(int i) {
        combine(2*i, left[i], right[i]);
        combine(2*i+1, left[i], right[i]);
        left[i] = 0, right[i] = INF;
    }
    // [ql, qr) is query range
    // [hl, hr] is query height values
    // [nl, nr) is node range of elements controlled
    void update(int ql, int qr, int hl, int hr, int node, int nl, int nr) {
        if (ql <= nl && nr <= qr) combine(node, hl, hr);
        else if (ql < nr && nl < qr) {
            propagate(node);
            int mid = (nl + nr) / 2;
            update(ql, qr, hl, hr, 2*node, nl, mid);
            update(ql, qr, hl, hr, 2*node+1, mid, nr);
        }
    }
    void queryAll(int node, int nl, int nr) {
        if (nl + 1 == nr) cout << left[node] << '\n';
        else {
            propagate(node);
            int mid = (nl + nr) / 2;
            queryAll(2*node, nl, mid);
            queryAll(2*node+1, mid, nr);
        }
    }
};

int main() {
    int n, k; cin >> n >> k;
    Segtree s(n);
    while (k--) {
        int t, ql, qr, h, hl, hr;
        cin>> t >> ql >> qr >> h;
        if (t == 1) hl = h, hr = INF;
        else hl = 0, hr = h;
        s.update(ql, qr+1, hl, hr, 1, 0, n);
    }
    s.queryAll(1, 0, n);
    return 0;
}