Submission #1007354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007354		jer033	Wall (IOI14_wall)	C++17	100 / 100	731 ms	224596 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

class SegTree{
public:
    int left_index;
    int right_index;
    int lo_value;
    int hi_value;
    int lo_update;
    int hi_update;
    SegTree* left_child;
    SegTree* right_child;

    SegTree(int l, int r)
    {
        left_index = l;
        right_index = r;
        lo_value = 0;
        hi_value = 0;
        lo_update = -1;
        hi_update = 999999;
        if (l==r)
        {
            left_child = nullptr;
            right_child = nullptr;
        }
        else
        {
            int m = (l+r)/2;
            left_child = new SegTree(l, m);
            right_child = new SegTree(m+1, r);
        }
    }

    void push()
    {
        if (hi_value < lo_update)
        {
            lo_value = lo_update;
            hi_value = lo_update;
        }
        else if (lo_value > hi_update)
        {
            lo_value = hi_update;
            hi_value = hi_update;
        }
        else
        {
            lo_value = max(lo_value, lo_update);
            hi_value = min(hi_value, hi_update);
        }

        if (left_child!=nullptr)
        {
            if (left_child->hi_update < lo_update)
            {
                left_child->lo_update = lo_update;
                left_child->hi_update = lo_update;
            }
            else if (left_child->lo_update > hi_update)
            {
                left_child->lo_update = hi_update;
                left_child->hi_update = hi_update;
            }
            else
            {
                left_child->lo_update = max(left_child->lo_update, lo_update);
                left_child->hi_update = min(left_child->hi_update, hi_update);
            }

            if (right_child->hi_update < lo_update)
            {
                right_child->lo_update = lo_update;
                right_child->hi_update = lo_update;
            }
            else if (right_child->lo_update > hi_update)
            {
                right_child->lo_update = hi_update;
                right_child->hi_update = hi_update;
            }
            else
            {
                right_child->lo_update = max(right_child->lo_update, lo_update);
                right_child->hi_update = min(right_child->hi_update, hi_update);
            }
        }
        lo_update = -1;
        hi_update = 999999;
    }

    void pull()
    {
        if (left_child != nullptr)
        {
            lo_value = min(left_child->lo_value, right_child->lo_value);
            hi_value = max(left_child->hi_value, right_child->hi_value);
        }
    }

    void modify_self(int typ, int h)
    {
        if (typ==1)
        {
            lo_update = h;
            if (hi_update < h)
                hi_update = h;
        }
        else
        {
            hi_update = h;
            if (lo_update > h)
                lo_update = h;
        }
    }

    void builder(int typ, int l, int r, int h)
    {
        //cout << "nakarating sa " << left_index << right_index << l << r << '\n';
        push();
        int mid_index = (left_index+right_index)/2;
        if ((l==left_index) and (r==right_index))
        {
            //grab_new_info();
            modify_self(typ, h);
            //update_children();
            //grab_new_info();
            //cout << "range is " << l << r << '\n';
        }
        else
        {
            push();
            if (l<=mid_index)
                left_child->builder(typ, l, min(mid_index, r), h);
            if (r>=(mid_index+1))
                right_child->builder(typ, max(l, mid_index+1), r, h);
            pull();
        }
    }

    void answer(int finalHeight[])
    {
        push();
        if (left_index == right_index)
        {
            finalHeight[left_index] = lo_value;
        }
        else
        {
            left_child->answer(finalHeight);
            right_child->answer(finalHeight);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree* seg = new SegTree(0, n-1);
    //cout << "nagawa\n";
    for (int oper = 0; oper<k; oper++)
    {
        int typ = op[oper];
        int l = left[oper];
        int r = right[oper];
        int h = height[oper];
        seg->builder(typ, l, r, h);
        //cout << "operation " << oper << " complete\n";
    }
    seg->answer(finalHeight);
}

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