Submission #612202

#	Time	Username	Problem	Language	Result	Execution time	Memory
612202		nohaxjustsoflo	Wall (IOI14_wall)	C++17	100 / 100	744 ms	100060 KiB

wall

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mxN = 2 * 1e5;

struct node
{
    int min, max, add, destruct;
};

struct segmentTree
{
    int size;
    vector<node> val;

    void build(int n, int index, int Lx, int Rx)
    {
        if(Rx - Lx == 1)
        {
            if(Lx < n)
            {
                val[index] = {0, 0, -1, -1};
            }
            else
            {
                val[index] = {INT_MAX, -INT_MAX, -1, -1};
            }
        }
        else
        {
            int m = (Lx + Rx) / 2;
            build(n, index * 2 + 1, Lx, m);
            build(n, index * 2 + 2, m, Rx);
            val[index] = {0, 0, -1, -1};
        }
    }

    void build(int n)
    {
        size = 1;
        while(size < n) size <<= 1;
        val = vector<node>(size * 2);
        build(n, 0, 0, size);
    }

    void add(int index, int h)
    {
        val[index].min = max(val[index].add, h);
        val[index].add = val[index].min;
        val[index].max = max(val[index].max, val[index].min);
        if(val[index].destruct != -1)
        {
            val[index].destruct = max(val[index].destruct, val[index].add);
        }
    }

    void destruct(int index, int h)
    {
        if(val[index].destruct != -1)
        {
            val[index].max = min(val[index].destruct, h);
        }
        else
        {
            val[index].max = h;
        }
        val[index].destruct = val[index].max;
        val[index].min =  min(val[index].min, val[index].max);
        if(val[index].add != -1)
        {
            val[index].add = min(val[index].add, val[index].destruct);
        }
    }

    node func(node left, node right)
    {
        return {min(left.min, right.min), max(left.max, right.max), -1, -1};
    }

    void add(int l, int r, int h, int index, int Lx, int Rx)
    {
        if(Rx <= l || Lx >= r) return;
        if(Lx >= l && Rx <= r)
        {
            add(index, h);
            return;
        }
        if(val[index].add != -1)
        {
            add(index * 2 + 1, val[index].add);
            add(index * 2 + 2, val[index].add);
            val[index].add = -1;
        }
        if(val[index].destruct != -1)
        {
            destruct(index * 2 + 1, val[index].destruct);
            destruct(index * 2 + 2, val[index].destruct);
            val[index].destruct = -1;
        }
        int m = (Rx + Lx) / 2;
        add(l, r, h, index * 2 + 1, Lx, m);
        add(l, r, h, index * 2 + 2, m, Rx);
        val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
    }

    void add(int l, int r, int h)
    {
        add(l, r, h, 0, 0, size);
    }

    void destruct(int l, int r, int h, int index, int Lx, int Rx)
    {
        if(Rx <= l || Lx >= r) return;
        if(Lx >= l && Rx <= r)
        {
            destruct(index, h);
            return;
        }
        if(val[index].destruct != -1)
        {
            destruct(index * 2 + 1, val[index].destruct);
            destruct(index * 2 + 2, val[index].destruct);
            val[index].destruct = -1;
        }
        if(val[index].add != -1)
        {
            add(index * 2 + 1, val[index].add);
            add(index * 2 + 2, val[index].add);
            val[index].add = -1;
        }
        int m = (Rx + Lx) / 2;
        destruct(l, r, h, index * 2 + 1, Lx, m);
        destruct(l, r, h, index * 2 + 2, m, Rx);
        val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
    }

    void destruct(int l, int r, int h)
    {
        destruct(l, r, h, 0, 0, size);
    }
    vector<int> ans;
    void print(int n, int index, int Lx, int Rx)
    {
        if(Rx - Lx == 1)
        {
            if(Lx < n)
            {
                ans.push_back(val[index].min);
            }
            return;
        }

        if(val[index].add != -1)
        {
            add(index * 2 + 1, val[index].add);
            add(index * 2 + 2, val[index].add);
            val[index].add = -1;
        }
        if(val[index].destruct != -1)
        {
            destruct(index * 2 + 1, val[index].destruct);
            destruct(index * 2 + 2, val[index].destruct);
            val[index].destruct = -1;
        }
        if(val[index].min == val[index].max && val[index].min != -1)
        {
            for(int i = 0; i < Rx - Lx; i++)
            {
                if(Lx + i < n)
                {
                    ans.push_back(val[index].min);
                }
                else
                {
                    break;
                }
            }
            return;
        }
        int m = (Rx + Lx) / 2;
        print(n, index * 2 + 1, Lx, m);
        print(n, index * 2 + 2, m, Rx);
    }

    void print(int n)
    {
        print(n, 0, 0, size);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    segmentTree st;
    st.build(n);
    for(int i=0; i<k; i++)
    {
        int o=op[i], l=left[i], r=right[i], h=height[i];
        r++;
        if(o == 1)
        {
            st.add(l, r, h);
        }
        else
        {
            st.destruct(l, r, h);
        }
    }
    st.print(n);
    for(int i=0; i<n; i++) finalHeight[i]=st.ans[i];
}

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