Submission #102747

#	Time	Username	Problem	Language	Result	Execution time	Memory
102747		naoai	Wall (IOI14_wall)	C++14	32 / 100	403 ms	20968 KiB

wall

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

using namespace std;

const int nmax = 1e5;
const int inf = 1 << 30;

static int v[nmax + 1];
static int aint[4 * nmax + 1];

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

    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] = min(aint[nod], val);
        return ;
    }

    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 build (int nod, int x, int y) {
    aint[nod] = inf;
    if (x == y)
        return ;

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

void dfs_min (int nod, int x, int y, int val = inf) {
    val = min(val, aint[nod]);

    if (x == y) {
        v[x] = min(val, v[x]);
        return ;
    }

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

void dfs_max (int nod, int x, int y, int val = -inf) {
    val = max(val, aint[nod]);

    if (x == y) {
        v[x] = max(val, v[x]);
        return ;
    }

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


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    if (n <= 10000 && k <= 5000) {
        for (int i = 0; i < k; ++ i) {
            for (int j = left[i]; j <= right[i]; ++ j) {
                if (op[i] == 1)
                    v[j] = max(v[j], height[i]);
                else
                    v[j] = min(v[j], height[i]);
            }
        }
    } else {
        int ind = 0;
        while (ind < k && op[ind] == 1) {
            update_max(1, 0, n - 1, left[ind], right[ind], height[ind]);
            ++ ind;
        }

        dfs_max(1, 0, n - 1);
        build(1, 0, n - 1);

        while (ind < k) {
            update_min(1, 0, n - 1, left[ind], right[ind], height[ind]);
            ++ ind;
        }
        dfs_min(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: 0 / 29
• Subtask 4: 0 / 39