Submission #700387

#	Time	Username	Problem	Language	Result	Execution time	Memory
700387		Cyanmond	Wall (IOI14_wall)	C++17	100 / 100	699 ms	141632 KiB

wall

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

constexpr int inf = 500000;

struct node {
    int l;
    int r;
    // clamp(a, l, r)
};
node merge(node a, node b) {
    a.l = std::min(b.r, a.l);
    a.r = std::min(b.r, a.r);
    a.l = std::max(b.l, a.l);
    a.r = std::max(b.l, a.r);
    return a;
}
node id = {-inf, inf};

int eval(int x, node p) {
    return std::max(p.l, std::min(p.r, x));
}

class segtree {
    int n, size;
    std::vector<node> data;

    void update(int i) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }

    public:
    segtree(int n_) : n(n_) {
        size = 1;
        while (size < n) {
            size *= 2;
        }
        data.assign(2 * size, id);
    }

    void edit(int i, node v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    node foldAll() {
        return data[1];
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    std::vector<std::vector<int>> addList(n + 1), eraseList(n + 1);
    for (int i = 0; i < k; ++i) {
        addList[left[i]].push_back(i);
        eraseList[right[i] + 1].push_back(i);
    }
    segtree seg(k);
    for (int i = 0; i < n; ++i) {
        for (const int x : addList[i]) {
            if (op[x] == 1) {
                seg.edit(x, {height[x], inf});
            } else {
                seg.edit(x, {-inf, height[x]});
            }
        }
        for (const int x : eraseList[i]) {
            seg.edit(x, id);
        }

        const auto res = seg.foldAll();
        finalHeight[i] = eval(0, res);
    }
}

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