Submission #804459

#	Time	Username	Problem	Language	Result	Execution time	Memory
804459		jakobrs	Wall (IOI14_wall)	C++17	100 / 100	619 ms	59240 KiB

wall

#include <vector>
#include <iostream>

int clamp(int low, int high, int x) {
    if (x < low) return low;
    if (x > high) return high;
    return x;
}

struct Req {
    int min = 0;
    int max = 2'000'000'000;

    Req operator*(Req rhs) const {
        return {
            .min = clamp(min, max, rhs.min),
            .max = clamp(min, max, rhs.max),
        };
    }
};

struct SegmentTree {
    std::vector<Req> values;
    int offset;

    explicit SegmentTree(int o) : values(2 * o, {0, 0}), offset(o) {}

    void push(int v) {
        values[2 * v] = values[v] * values[2 * v];
        values[2 * v + 1] = values[v] * values[2 * v + 1];
        values[v] = Req{};
    }

    void update(int l, int r, Req upd) { update(l, r, upd, 1, 0, offset); }

    void update(int l, int r, Req upd, int v, int s, int e) {
        if (e <= l || r <= s) {
            return;
        } else if (l <= s && e <= r) {
            values[v] = upd * values[v];
        } else {
            int m = (s + e) / 2;
            push(v);
            update(l, r, upd, 2 * v, s, m);
            update(l, r, upd, 2 * v + 1, m, e);
            values[v] = Req{};
        }
    }

    void canonicalise() {
        for (int i = 1; i < offset; i++) push(i);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
    int o = 1;
    while (o < n) o *= 2;
    SegmentTree st(o);

    for (int i = 0; i < k; i++) {
        int l = left[i];
        int r = right[i] + 1;

        Req upd;
        if (op[i] == 1) upd.min = height[i];
        if (op[i] == 2) upd.max = height[i];

        st.update(l, r, upd);
    }

    st.canonicalise();
    for (int i = 0; i < n; i++) finalHeight[i] = st.values[i + o].min;
}

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