Submission #538364

#	Time	Username	Problem	Language	Result	Execution time	Memory
538364		timreizin	Wall (IOI14_wall)	C++17	100 / 100	1658 ms	151740 KiB

wall

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

using namespace std;

struct SegTree
{
    int n;
    vector<pair<int, int>> tree;
    vector<pair<int, int>> mod;

    SegTree(int _n) : n(_n)
    {
        tree.resize(4 * n + 5, {0, 1e5});
        mod.resize(4 * n + 5, {0, 1e5});
    }

    void push(int v)
    {
        tree[v << 1].first = max(tree[v << 1].first, mod[v].first);
        tree[v << 1].second = max(tree[v << 1].second, mod[v].first);
        tree[v << 1 | 1].first = max(tree[v << 1 | 1].first, mod[v].first);
        tree[v << 1 | 1].second = max(tree[v << 1 | 1].second, mod[v].first);
        tree[v << 1].first = min(tree[v << 1].first, mod[v].second);
        tree[v << 1].second = min(tree[v << 1].second, mod[v].second);
        tree[v << 1 | 1].first = min(tree[v << 1 | 1].first, mod[v].second);
        tree[v << 1 | 1].second = min(tree[v << 1 | 1].second, mod[v].second);
        mod[v << 1].first = max(mod[v << 1].first, mod[v].first);
        mod[v << 1].second = max(mod[v << 1].second, mod[v].first);
        mod[v << 1 | 1].first = max(mod[v << 1 | 1].first, mod[v].first);
        mod[v << 1 | 1].second = max(mod[v << 1 | 1].second, mod[v].first);
        mod[v << 1].first = min(mod[v << 1].first, mod[v].second);
        mod[v << 1].second = min(mod[v << 1].second, mod[v].second);
        mod[v << 1 | 1].first = min(mod[v << 1 | 1].first, mod[v].second);
        mod[v << 1 | 1].second = min(mod[v << 1 | 1].second, mod[v].second);
        mod[v] = {0, 1e5};
    }

    void updateMax(int a, int b, int val, int v, int l, int r)
    {
        if (a > r || b < l) return;
        if (a == l && b == r)
        {
            //make >= val
            tree[v].first = max(tree[v].first, val);
            tree[v].second = max(tree[v].second, val);
            mod[v].first = max(mod[v].first, val);
            mod[v].second = max(mod[v].second, val);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        updateMax(a, min(b, m), val, v << 1, l, m);
        updateMax(max(a, m + 1), b, val, v << 1 | 1, m + 1, r);
    }

    void updateMax(int a, int b, int val)
    {
        updateMax(a, b, val, 1, 0, n - 1);
    }

    void updateMin(int a, int b, int val, int v, int l, int r)
    {
        if (a > r || b < l) return;
        if (a == l && b == r)
        {
            //make <= val
            tree[v].first = min(tree[v].first, val);
            tree[v].second = min(tree[v].second, val);
            mod[v].first = min(mod[v].first, val);
            mod[v].second = min(mod[v].second, val);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        updateMin(a, min(b, m), val, v << 1, l, m);
        updateMin(max(a, m + 1), b, val, v << 1 | 1, m + 1, r);
    }

    void updateMin(int a, int b, int val)
    {
        updateMin(a, b, val, 1, 0, n - 1);
    }

    pair<int, int> get(int p, int v, int l, int r)
    {
        if (l == r) return tree[v];
        push(v);
        int m = (l + r) >> 1;
        if (p <= m) return get(p, v << 1, l, m);
        return get(p, v << 1 | 1, m + 1, r);
    }

    int get(int p)
    {
        auto [l, r] = get(p, 1, 0, n - 1);
        return l;
    }

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree st(n);
    for (int i = 0; i < k; ++i)
    {
        if (op[i] == 1) st.updateMax(left[i], right[i], height[i]);
        else st.updateMin(left[i], right[i], height[i]);
    }
    for (int i = 0; i < n; ++i) finalHeight[i] = st.get(i);
}

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