Submission #1007316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007316		jer033	Wall (IOI14_wall)	C++17	0 / 100	117 ms	13856 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;
    SegTree* left_child;
    SegTree* right_child;
    SegTree* parent;

    SegTree(int l, int r, SegTree* magulang)
    {
        parent = magulang;
        left_index = l;
        right_index = r;
        lo_value = 0;
        hi_value = 0;
        if (l==r)
        {
            left_child = nullptr;
            right_child = nullptr;
        }
        else
        {
            int m = (l+r)/2;
            left_child = new SegTree(l, m, this);
            right_child = new SegTree(m+1, r, this);
        }
    }

    void update_self()
    {
        if (parent!=nullptr)
        {
            if (hi_value < parent->lo_value)
            {
                lo_value = parent->lo_value;
                hi_value = parent->lo_value;
            }
            else if (lo_value > parent->hi_value)
            {
                lo_value = parent->hi_value;
                hi_value = parent->hi_value;
            }
            else
            {
                lo_value = max(lo_value, parent->lo_value);
                hi_value = min(hi_value, parent->hi_value);
            }
        }

    }

    void grab_new_info()
    {
        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 rep_grab_new_info()
    {
        grab_new_info();
        if (parent!=nullptr)
            parent->rep_grab_new_info();
    }

    void update_children()
    {
        //grab_new_info();
        if (left_child!=nullptr)
        {
            left_child->update_self();
            right_child->update_self();
        }
    }

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

    void builder(int typ, int l, int r, int h)
    {
        //cout << "nakarating sa " << left_index << right_index << l << r << '\n';
        //update_children();
        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
        {
            update_children();
            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);
            grab_new_info();
        }
    }

    void answer(int finalHeight[])
    {
        update_self();
        if (left_index == right_index)
        {
            finalHeight[left_index] = lo_value;
        }
        else
        {
            //update_children();
            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, nullptr);
    //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: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39