제출 #104140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104140		naoai	벽 (IOI14_wall)	C++14	100 / 100	953 ms	107056 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e6;
const int inf = 1 << 30;

static int v[nmax + 1];

struct str {
    int mn, mx;

    str () {
        mn = inf;
        mx = -inf;
    }
} aint[4 * nmax + 1];

void propaga (int nod) {
    for (int i = 0; i < 2; ++ i) {
        aint[2 * nod + i].mx = min(aint[2 * nod + i].mx, aint[nod].mn);
        aint[2 * nod + i].mn = min(aint[2 * nod + i].mn, aint[nod].mn);

        aint[2 * nod + i].mx = max(aint[2 * nod + i].mx, aint[nod].mx);
        aint[2 * nod + i].mn = max(aint[2 * nod + i].mn, aint[nod].mx);
    }

    aint[nod] = str();
}

void update_max (int nod, int x, int y, int st, int dr, int val) {
    if (st <= x && y <= dr) {
        aint[nod].mx = max(aint[nod].mx, val);
        aint[nod].mn = max(aint[nod].mn, val);
        return ;
    }

    propaga(nod);

    int mij = (x + y) / 2;
    if (st <= mij)
        update_max(2 * nod, x, mij, st, dr, val);
    if (mij < dr)
        update_max(2 * nod + 1, mij + 1, y, st, dr, val);
}

void update_min (int nod, int x, int y, int st, int dr, int val) {
    if (st <= x && y <= dr) {
        aint[nod].mx = min(aint[nod].mx, val);
        aint[nod].mn = min(aint[nod].mn, val);
        return ;
    }

    propaga(nod);

    int mij = (x + y) / 2;
    if (st <= mij)
        update_min(2 * nod, x, mij, st, dr, val);
    if (mij < dr)
        update_min(2 * nod + 1, mij + 1, y, st, dr, val);
}

void dfs (int nod, int x, int y) {
    if (x == y) {
        v[x] = max(aint[nod].mx, min(0, aint[nod].mn));
        return ;
    }

    propaga(nod);

    int mij = (x + y) / 2;
    dfs(2 * nod, x, mij);
    dfs(2 * nod + 1, mij + 1, y);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; ++ i) {
        if (op[i] == 1)
            update_max(1, 0, n - 1, left[i], right[i], height[i]);
        else
            update_min(1, 0, n - 1, left[i], right[i], height[i]);
    }

    dfs(1, 0, n - 1);

    for (int i = 0; i < n; ++ i)
        finalHeight[i] = v[i];
    return;
}

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