Submission #1016659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016659		NValchanov	Wall (IOI14_wall)	C++17	0 / 100	173 ms	217424 KiB

wall

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

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 2e6 + 10;
const int MAXQ = 5e5 + 10;
const int MAXH = 1e5 + 10;
const int INF = 1e9 + 10;

struct SegmentTree
{
    struct node
    {
        int lazy;
        int minel;
        int maxel;

        node()
        {
            lazy = INF;
            minel = 0;
            maxel = 0;
        }
        node(int x)
        {
            minel = maxel = x;
        }

        friend node operator+(node Lnode, node Rnode)
        {
            node result;

            result.lazy = INF;
            result.minel = min(Lnode.minel, Rnode.minel);
            result.maxel = max(Lnode.maxel, Rnode.maxel);

            return result;
        }
    };

    node tree[4 * MAXN];
    int h[MAXN];
    int n;

    SegmentTree()
    {
        n = 0;
    }

    SegmentTree(int _n)
    {
        n = _n;
    }

    void push_lazy(int left, int right, int idx)
    {
        if(tree[idx].lazy == INF)
            return;

        tree[idx] = node(tree[idx].lazy);

        if(left != right)
        {
            tree[2 * idx].lazy = tree[2 * idx + 1].lazy = tree[idx].lazy;
        }

        tree[idx].lazy = INF;
    }

    void update_max(int left, int right, int idx, int qleft, int qright, int val)
    {
        push_lazy(left, right, idx);

        if(qright < left || right < qleft)
            return;

        if(tree[idx].minel >= val)
            return;

        if(qleft <= left && right <= qright && tree[idx].maxel <= val)
        {
            tree[idx].lazy = val;
            push_lazy(left, right, idx);
            return;
        }

        int mid = left + (right - left) / 2;

        update_max(left, mid, 2 * idx, qleft, qright, val);
        update_max(mid + 1, right, 2 * idx + 1, qleft, qright, val);

        tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
    }

    void update_min(int left, int right, int idx, int qleft, int qright, int val)
    {
        push_lazy(left, right, idx);

        if(qright < left || right < qleft)
            return;

        if(tree[idx].maxel <= val)
            return;

        if(qleft <= left && right <= qright && tree[idx].minel >= val)
        {
            tree[idx].lazy = val;
            push_lazy(left, right, idx);
            return;
        }

        int mid = left + (right - left) / 2;

        update_min(left, mid, 2 * idx, qleft, qright, val);
        update_min(mid + 1, right, 2 * idx + 1, qleft, qright, val);

        tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
    }

    void build(int left, int right, int idx)
    {
        push_lazy(left, right, idx);

        if(left == right)
        {
            h[left] = tree[idx].minel;
            return;
        }

        int mid = left + (right - left) / 2;

        build(left, mid, 2 * idx);
        build(mid + 1, right, 2 * idx + 1);
    }

    void update_max(int left, int right, int val)
    {
        update_max(1, n, 1, left, right, val);
    }

    void update_min(int left, int right, int val)
    {
        update_min(1, n, 1, left, right, val);
    }

    void build()
    {
        build(1, n, 1);
    }

    void query(int type, int left, int right, int val)
    {
        if(type == 1)
            update_max(left, right, val);
        else
            update_min(left, right, val);
    }

    int access(int idx)
    {
        return h[idx + 1];
    }
};

SegmentTree st;

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[])
{
    st = SegmentTree(n);

    for(int i = 0; i < q; i++)
    {
        st.query(op[i], left[i] + 1, right[i] + 1, height[i]);
    }

    st.build();

    for(int i = 0; i < n; i++)
    {
        finalHeight[i] = st.access(i);
    }
}

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