Submission #1016695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016695		NValchanov	Wall (IOI14_wall)	C++17	100 / 100	470 ms	138576 KiB

wall

#include <bits/stdc++.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;
        }
    };

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

    SegmentTree()
    {
        n = 0;
    }

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

        tree[idx].minel = tree[idx].maxel = 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].minel = min(tree[2 * idx].minel, tree[2 * idx + 1].minel);
        tree[idx].maxel = max(tree[2 * idx].maxel, tree[2 * idx + 1].maxel);
    }

    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].minel = min(tree[2 * idx].minel, tree[2 * idx + 1].minel);
        tree[idx].maxel = max(tree[2 * idx].maxel, tree[2 * idx + 1].maxel);
    }

    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 if(type == 2)
            update_min(left, right, val);
        else
            assert(false);
    }

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

SegmentTree st;

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

    for(int i = 0; i < k; 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);
    }
}

// int op[MAXN];
// int l[MAXN];
// int r[MAXN];
// int height[MAXN];
// int finalHeight[MAXN];
// int n, k;

// int main()
// {
//     cin >> n >> k;

//     for(int i = 0; i < k; i++)
//     {
//         cin >> op[i] >> l[i] >> r[i] >> height[i];
//     }

//     buildWall(n, k, op, l, r, height, finalHeight);

//     for(int i = 0; i < n; i++)
//     {
//         cout << finalHeight[i] << " ";
//     }
//     cout << endl;

//     return 0;
// }

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