Submission #1148730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148730		BlockOG	Wall (IOI14_wall)	C++20	24 / 100	449 ms	11676 KiB

wall

// mrrrow mnyaa ;3c
// go play vivid/stasis! it's a really awesome free game on steam

enum Type {
    UnMarked,
    Max,
    Min,
    Set,
    Clamp,
};

const int N = 1 << 21;
int st[N * 2][3];

void merge(int i, Type o, int a, int b = 0) {
    switch (st[i][0]) {
    case Type::UnMarked:
        st[i][0] = o;
        st[i][1] = a;
        st[i][2] = b;
        break;
    case Type::Max:
        switch (o) {
        case Type::Max:
            if (a > st[i][1]) st[i][1] = a;
            break;
        case Type::Min:
            if (a <= st[i][1]) st[i][0] = Type::Set, st[i][1] = a;
            else st[i][0] = Type::Clamp, st[i][2] = a;
            break;
        case Type::Set:
            st[i][0] = Type::Set;
            st[i][1] = a;
            break;
        case Type::Clamp:
            if (st[i][1] > b) st[i][0] = Type::Set, st[i][1] = b;
            else st[i][0] = Type::Clamp, st[i][1] = st[i][1] > a ? st[i][1] : a, st[i][2] = b;
            break;
        }
        break;
    case Type::Min:
        switch (o) {
        case Type::Max:
            if (a >= st[i][2]) st[i][0] = Type::Set, st[i][1] = a;
            else st[i][0] = Type::Clamp, st[i][2] = st[i][1], st[i][1] = a;
            break;
        case Type::Min:
            if (a < st[i][1]) st[i][1] = a;
            break;
        case Type::Set:
            st[i][0] = Type::Set;
            st[i][1] = a;
            break;
        case Type::Clamp:
            if (st[i][1] < a) st[i][0] = Type::Set, st[i][1] = a;
            else st[i][0] = Type::Clamp, st[i][1] = a, st[i][2] = st[i][2] < b ? st[i][2] : b;
            break;
        }
        break;
    case Type::Set:
        switch (o) {
        case Type::Max:
            st[i][1] = st[i][1] > a ? st[i][1] : a;
            break;
        case Type::Min:
            st[i][1] = st[i][1] < a ? st[i][1] : a;
            break;
        case Type::Set:
            st[i][1] = a;
            break;
        case Type::Clamp:
            st[i][1] = st[i][1] <= a ? a : st[i][1] >= b ? b : st[i][1];
            break;
        }
        break;
    case Type::Clamp:
        switch (o) {
        case Type::Max:
            if (st[i][2] <= a) st[i][0] = Type::Set, st[i][1] = a;
            else st[i][1] = st[i][1] > a ? st[i][1] : a;
            break;
        case Type::Min:
            if (st[i][1] >= a) st[i][0] = Type::Set, st[i][1] = a;
            else st[i][2] = st[i][2] < a ? st[i][2] : a;
            break;
        case Type::Set:
            st[i][0] = Type::Set;
            st[i][1] = a;
            break;
        case Type::Clamp:
            if (st[i][1] >= b) st[i][0] = Type::Set, st[i][1] = b;
            else if (st[i][2] <= a) st[i][0] = Type::Set, st[i][1] = a;
            else st[i][1] = st[i][1] > a ? st[i][1] : a, st[i][2] = st[i][2] < b ? st[i][2] : b;
            break;
        }
        break;
    }
}

void push(int i) {
    if (st[i][0] == Type::UnMarked) return;

    merge(i * 2, (Type)st[i][0], st[i][1], st[i][2]);
    merge(i * 2 + 1, (Type)st[i][0], st[i][1], st[i][2]);
    st[i][0] = Type::UnMarked;
}

void update(Type o, int v, int l, int r, int i = 1, int cl = 0, int cr = N - 1) {
    if (l <= cl && cr <= r) {
        merge(i, o, v);
        return;
    }

    push(i);

    int me = (cl + cr) / 2;
    int ms = me + 1;

    if (l <= me && cl <= r) update(o, v, l, r, i * 2, cl, me);
    if (l <= cr && ms <= r) update(o, v, l, r, i * 2 + 1, ms, cr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int it = 0; it < k; it++) update((Type)op[it], height[it], left[it], right[it]);

    for (int i = 0; i < n; i++) {
        for (int j = N + i; j; j /= 2) {
            switch (st[j][0]) {
            case Type::Max:
                finalHeight[i] = finalHeight[i] > st[j][1] ? finalHeight[i] : st[j][1];
                break;
            case Type::Min:
                finalHeight[i] = finalHeight[i] < st[j][1] ? finalHeight[i] : st[j][1];
                break;
            case Type::Set:
                finalHeight[i] = st[j][1];
                break;
            case Type::Clamp:
                finalHeight[i] = finalHeight[i] <= st[j][1] ? st[j][1] : finalHeight[i] >= st[j][2] ? st[j][2] : finalHeight[i];
                break;
            }
        }
    }
}

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