oj.uz

Submission #466961

# Submission time Handle Problem Language Result Execution time Memory
466961 2021-08-21T04:19:23 Z Rico64 Wall (IOI14_wall) C++14
100 / 100
 847 ms 86016 KB 
//
// 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 5 ms 956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 166 ms 13948 KB Output is correct
3 Correct 197 ms 8300 KB Output is correct
4 Correct 511 ms 21456 KB Output is correct
5 Correct 326 ms 22468 KB Output is correct
6 Correct 317 ms 20836 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 8 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 166 ms 13860 KB Output is correct
9 Correct 181 ms 8260 KB Output is correct
10 Correct 523 ms 21376 KB Output is correct
11 Correct 324 ms 22528 KB Output is correct
12 Correct 326 ms 20864 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 171 ms 13968 KB Output is correct
15 Correct 36 ms 2288 KB Output is correct
16 Correct 627 ms 21732 KB Output is correct
17 Correct 325 ms 21060 KB Output is correct
18 Correct 322 ms 21052 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 5 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 179 ms 13888 KB Output is correct
9 Correct 184 ms 8236 KB Output is correct
10 Correct 528 ms 21372 KB Output is correct
11 Correct 335 ms 22468 KB Output is correct
12 Correct 313 ms 20892 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 171 ms 14008 KB Output is correct
15 Correct 35 ms 2284 KB Output is correct
16 Correct 619 ms 21824 KB Output is correct
17 Correct 324 ms 21060 KB Output is correct
18 Correct 329 ms 21112 KB Output is correct
19 Correct 774 ms 86016 KB Output is correct
20 Correct 779 ms 83436 KB Output is correct
21 Correct 847 ms 85884 KB Output is correct
22 Correct 830 ms 83444 KB Output is correct
23 Correct 815 ms 83440 KB Output is correct
24 Correct 777 ms 83424 KB Output is correct
25 Correct 777 ms 83396 KB Output is correct
26 Correct 818 ms 85896 KB Output is correct
27 Correct 811 ms 85872 KB Output is correct
28 Correct 796 ms 83356 KB Output is correct
29 Correct 783 ms 83424 KB Output is correct
30 Correct 772 ms 83440 KB Output is correct