제출 #1148732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148732		BlockOG	Wall (IOI14_wall)	C++20	100 / 100	416 ms	61544 KiB

wall

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

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

void merge(int i, int a, int b) {
    if (st[i][0]) {
        st[i][1] = st[i][1] <= a ? a : st[i][1] >= b ? b : st[i][1];
        st[i][2] = st[i][2] <= a ? a : st[i][2] >= b ? b : st[i][2];
    } else {
        st[i][0] = true;
        st[i][1] = a;
        st[i][2] = b;
    }
}

void push(int i) {
    if (!st[i][0]) return;
    st[i][0] = false;

    merge(i * 2, st[i][1], st[i][2]);
    merge(i * 2 + 1, st[i][1], st[i][2]);
}

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

    push(i);

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

    if (l <= me && cl <= r) update(a, b, l, r, i * 2, cl, me);
    if (l <= cr && ms <= r) update(a, b, 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(op[it] == 1 ? height[it] : -0x80000000, op[it] == 2 ? height[it] : 0x7fffffff, left[it], right[it]);

    for (int i = 0; i < n; i++) {
        for (int j = N + i; j; j /= 2) {
            if (st[j][0]) {
                finalHeight[i] = finalHeight[i] <= st[j][1] ? st[j][1] : finalHeight[i] >= st[j][2] ? st[j][2] : finalHeight[i];
            }
        }
    }
}

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