Submission #103001

#	Time	Username	Problem	Language	Result	Execution time	Memory
103001		alexpetrescu	Wall (IOI14_wall)	C++14	100 / 100	818 ms	77136 KiB

wall

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

#define MAXN 2000000
#define MAXP 4200000
#define INF 100000

int atLeast[MAXP], atMost[MAXP], ans[MAXN], left, right, h, tip;

inline void unu(int p, int h) {
    atLeast[p] = std::max(atLeast[p], h);
    atMost[p] = std::max(atMost[p], atLeast[p]);
}

inline void doi(int p, int h) {
    atMost[p] = std::min(atMost[p], h);
    atLeast[p] = std::min(atLeast[p], atMost[p]);
}

inline void propag(int p, int st, int dr) {
    unu(st, atLeast[p]);
    doi(st, atMost[p]);
    unu(dr, atLeast[p]);
    doi(dr, atMost[p]);
    atLeast[p] = 0;
    atMost[p] = INF;
}

void update(int p, int st, int dr) {
    if (left <= st && dr <= right) {
        if (tip == 1)
            unu(p, h);
        else
            doi(p, h);
    } else {
        propag(p, 2 * p, 2 * p + 1);
        int m = (st + dr) / 2;
        if (left <= m) update(2 * p, st, m);
        if (m < right) update(2 * p + 1, m + 1, dr);
    }
}

void dfs(int p, int st, int dr) {
    if (st == dr)
        ans[st] = atLeast[p];
    else {
        propag(p, 2 * p, 2 * p + 1);
        int m = (st + dr) / 2;
        dfs(2 * p, st, m);
        dfs(2 * p + 1, m + 1, dr);
    }
}

void buildWall(int n, int k, int op[], int left0[], int right0[], int height[], int finalHeight[]) {
    for (int i = 0; i < k; i++) {
        tip = op[i];
        left = left0[i];
        right = right0[i];
        h = height[i];
        update(1, 0, n - 1);
    }
    dfs(1, 0, n - 1);
    for (int i = 0; i < n; i++)
        finalHeight[i] = ans[i];
}

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