Submission #405656

#	Time	Username	Problem	Language	Result	Execution time	Memory
405656		fvogel499	Wall (IOI14_wall)	C++14	100 / 100	2330 ms	63636 KiB

wall

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define ll long long
#define rint int32_t

const int pow2 = 1<<21;

int minLz [pow2*2];
int maxLz [pow2*2];

void btClear() {
    for (int i = 0; i < pow2*2; i++) {
        minLz[i] = 0;
        maxLz[i] = 100000;
    }
}

void btPrpg(int qNode) {
    if (qNode >= pow2) return;

    if (minLz[qNode*2] < minLz[qNode]) minLz[qNode*2] = minLz[qNode];
    if (maxLz[qNode*2] > maxLz[qNode]) maxLz[qNode*2] = maxLz[qNode];
    if (minLz[qNode*2] > maxLz[qNode*2]) {
        if (minLz[qNode*2] <= minLz[qNode]) maxLz[qNode*2] = minLz[qNode];
        else minLz[qNode*2] = maxLz[qNode];
    }

    if (minLz[qNode*2+1] < minLz[qNode]) minLz[qNode*2+1] = minLz[qNode];
    if (maxLz[qNode*2+1] > maxLz[qNode]) maxLz[qNode*2+1] = maxLz[qNode];
    if (minLz[qNode*2+1] > maxLz[qNode*2+1]) {
        if (minLz[qNode*2+1] <= minLz[qNode]) maxLz[qNode*2+1] = minLz[qNode];
        else minLz[qNode*2+1] = maxLz[qNode];
    }

    minLz[qNode] = 0;
    maxLz[qNode] = 100000;
}

void btUpdate(int rBegin, int rEnd, int rUp, int rVal, int qNode, int qBegin, int qEnd) {
    if (rBegin > qEnd or qBegin > rEnd) return;
    else if (rBegin <= qBegin and qEnd <= rEnd) {
        if (rUp == 1 and minLz[qNode] < rVal) {
            minLz[qNode] = rVal;
            if (minLz[qNode] > maxLz[qNode]) {
                maxLz[qNode] = rVal;
            }
        }
        else if (rUp == 2 and maxLz[qNode] > rVal) {
            maxLz[qNode] = rVal;
            if (minLz[qNode] > maxLz[qNode]) {
                minLz[qNode] = rVal;
            }
        }
        btPrpg(qNode);
    }
    else {
        btPrpg(qNode);
        int qMid = (qBegin+qEnd)/2;
        btUpdate(rBegin, rEnd, rUp, rVal, qNode*2, qBegin, qMid);
        btUpdate(rBegin, rEnd, rUp, rVal, qNode*2+1, qMid+1, qEnd);
    }
}

void buildWall(int n, int nbReq, int up [], int left [], int right [], int height [], int res []) {
    btClear();
    for (int i = 0; i < n; i++) btUpdate(i, i, 2, 0, 1, 0, pow2-1);
    for (int i = 0; i < nbReq; i++) {
        // if (up[i] == 2) continue;
        btUpdate(left[i], right[i], up[i], height[i], 1, 0, pow2-1);
    }
    for (int i = 0; i < n; i++) {
        btUpdate(i, i, 1, 0, 1, 0, pow2-1);
        res[i] = minLz[pow2+i];
        // cout << "--> " << minLz[pow2+i] << "  -  " << maxLz[pow2+i] << endl; // dbg info
    }
    int d = 0;
    d++;
}

// rint main() {
//     cin.tie(0);
//     ios_base::sync_with_stdio(0);

//     int n = 10;
//     int nbReq = 6;
//     int up [6] = {1, 2, 2, 1, 1, 2};
//     int left [6] = {1, 4, 3, 0, 2, 6};
//     int right [6] = {8, 9, 6, 5, 2, 7};
//     int height [6] = {4, 1, 5, 3, 5, 0};
//     int res [6];
//     buildWall(n, nbReq, up, left, right, height, res);

//     int d = 0;
//     d++;
// }

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