Submission #198603

#	Time	Username	Problem	Language	Result	Execution time	Memory
198603		DS007	Wall (IOI14_wall)	C++14	32 / 100	1198 ms	52216 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>
using namespace std;

const int N = 2e6;
int upper[N * 8], lower[N * 8], ans[N];

void push(int v) {
    upper[v] = min(upper[v], lower[v]);
    upper[v * 2] = min(upper[v * 2], lower[v * 2]);
    upper[v * 2 + 1] = min(upper[v * 2 + 1], lower[v * 2 + 1]);
    upper[v * 2] = max(upper[v * 2], upper[v]);
    upper[v * 2 + 1] = max(upper[v * 2 + 1], upper[v]);
    lower[v * 4] = min(lower[v * 2], lower[v * 4]);
    lower[v * 4 + 1] = min(lower[v * 4 + 1], lower[v * 2]);
    lower[v * 4 + 2] = min(lower[v * 4 + 2], lower[v * 2 + 1]);
    lower[v * 4 + 3] = min(lower[v * 4 + 3], lower[v * 2 + 1]);
    lower[v * 2] = lower[v];
    lower[v * 2 + 1] = lower[v];
    upper[v] = 0;
    lower[v] = 1e9;
}

void update(int v, int l, int r, int tl, int tr, int val) {
    if (tl > tr)
        return;
    else if (l != r)
        push(v);

    if (l == tl && r == tr) {
        if (val > 0)
            upper[v] = max(upper[v], val), lower[v] = 1e9;
        else
            lower[v] = min(lower[v], -val);
        return;
    }

    int mid = (l + r) / 2;
    update(v * 2, l, mid, tl, min(mid, tr), val);
    update(v * 2 + 1, mid + 1, r, max(mid + 1, tl), tr, val);
}

void query(int v, int l, int r) {
    if (l == r) {
        ans[l] = min(upper[v], lower[v]);
        return;
    }

    push(v);
    int mid = (l + r) / 2;
    query(v * 2, l, mid);
    query(v * 2 + 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    fill(lower, lower + 4 * N, 1e9);

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

    query(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: 0 / 29
• Subtask 4: 0 / 39