Submission #466961

#	Time	Username	Problem	Language	Result	Execution time	Memory
466961		Rico64	Wall (IOI14_wall)	C++14	100 / 100	847 ms	86016 KiB

wall

//
// Created by Rico on 8/20/2021.
//

#include <iostream>
#include "wall.h"

const int MAX_LBEG2 = 4194304;

using namespace std;


int lbeg;
int sizes[MAX_LBEG2];
int mns[MAX_LBEG2], mxs[MAX_LBEG2];

void addto(int cmn, int cmx, int nmn, int nmx, int& fmn, int& fmx) {
    if (nmn > cmx) {
        fmn = fmx = nmn;
    } else if (cmn > nmx) {
        fmn = fmx = nmx;
    } else {
        fmn = max(cmn, nmn);
        fmx = min(cmx, nmx);
    }
}

void pushdown(int i) {
    addto(mns[i << 1], mxs[i << 1], mns[i], mxs[i], mns[i << 1], mxs[i << 1]);
    addto(mns[i << 1 ^ 1], mxs[i << 1 ^ 1], mns[i], mxs[i], mns[i << 1 ^ 1], mxs[i << 1 ^ 1]);
    mns[i] = INT32_MIN;
    mxs[i] = INT32_MAX;
}

void qadd(int i, int l, int r, const int& h) {
    if (l >= sizes[i] || r <= 0) return;
    if (l <= 0 && r >= sizes[i]) {
        if (h > mxs[i]) {
            mns[i] = mxs[i] = h;
        } else {
            mns[i] = max(mns[i], h);
        }
        return;
    }
    pushdown(i);
    qadd(i << 1, l, r, h);
    qadd(i << 1 ^ 1, l - sizes[i << 1], r - sizes[i << 1], h);
}

void qremove(int i, int l, int r, const int& h) {
    if (l >= sizes[i] || r <= 0) return;
    if (l <= 0 && r >= sizes[i]) {
        if (h < mns[i]) {
            mns[i] = mxs[i] = h;
        } else {
            mxs[i] = min(mxs[i], h);
        }
        return;
    }
    pushdown(i);
    qremove(i << 1, l, r, h);
    qremove(i << 1 ^ 1, l - sizes[i << 1], r - sizes[i << 1], h);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (lbeg = 1; lbeg < n; lbeg <<= 1);
    fill(sizes + lbeg, sizes + (lbeg + n), 1);
    fill(sizes + (lbeg + n), sizes + (lbeg << 1), 0);
    for (int i = lbeg - 1; i > 0; --i) sizes[i] = sizes[i << 1] + sizes[i << 1 ^ 1];
    fill(mns, mns + lbeg, INT32_MIN);
    fill(mns + lbeg, mns + (lbeg << 1), 0);
    fill(mxs, mxs + lbeg, INT32_MAX);
    fill(mxs + lbeg, mxs + (lbeg << 1), 0);

    for (int it = 0, type; it < k; ++it) {
        type = op[it];
        if (type == 1) {
            qadd(1, left[it], right[it] + 1, height[it]);
        } else if (type == 2) {
            qremove(1, left[it], right[it] + 1, height[it]);
        }
    }

    for (int i = 1; i < lbeg; ++i) {
        pushdown(i);
    }
    for (int i = lbeg; i < lbeg + n; ++i) {
        finalHeight[i - lbeg] = mns[i];
    }
}

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