Submission #289157

#	Time	Username	Problem	Language	Result	Execution time	Memory
289157		stoyan_malinin	Wall (IOI14_wall)	C++14	100 / 100	1527 ms	201336 KiB

wall

#include "wall.h"
//#include "grader.cpp"

#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 2e6 + 5;

struct Range
{
    int l, r;

    Range(){}
    Range(int l, int r)
    {
        this->l = l;
        this->r = r;
    }

    int f(int x)
    {
        if(x<=l) return l;
        if(x>=r) return r;
        return x;
    }
};

Range Merge(Range first, Range second)
{
    if(second.l>=first.r) return Range(second.l, second.l);
    if(second.r<=first.l) return Range(second.r, second.r);
    if(second.l<=first.l && first.r<=second.r) return Range(first.l, first.r);
    if(first.l<=second.l && second.r<=first.r) return Range(second.l, second.r);
    if(first.l<=second.l && first.r<=second.r && second.l<=first.r) return Range(second.l, first.r);
    if(second.l<=first.l && second.r<=first.r && first.l<=second.r) return Range(first.l, second.r);
}

struct SegmentTree
{
    Range val;

    int l, r;
    SegmentTree *L, *R;

    SegmentTree(){}
    SegmentTree(int l, int r)
    {
        this->val = Range(0, MAXN);
        this->l = l;
        this->r = r;

        this->L = nullptr;
        this->R = nullptr;
    }

    void build()
    {
        if(l==r) return;

        L = new SegmentTree(l, (l+r)/2);
        R = new SegmentTree((l+r)/2+1, r);

        L->build();
        R->build();
    }

    void rem(int q)
    {
        if(l==r && q==l)
        {
            val = Range(0, MAXN);
            return;
        }
        if(q<l || q>r) return;

        L->rem(q);
        R->rem(q);
        val = Merge(L->val, R->val);
    }

    void add(int q, Range newVal)
    {
        if(l==r && q==l)
        {
            val = newVal;
            return;
        }
        if(q<l || q>r) return;

        L->add(q, newVal);
        R->add(q, newVal);
        val = Merge(L->val, R->val);
    }

    void reset()
    {
        //if(val==Range(0, MAXN)) return;
        val = Range(0, MAXN);

        if(L!=nullptr)
        {
            L->reset();
            R->reset();
        }
    }
};

vector <int> toRemove[MAXN], toAdd[MAXN];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegmentTree *T = new SegmentTree(0, k-1);
    T->build();

    for(int i = 0;i<k;i++)
    {
        toAdd[ left[i] ].push_back(i);
        toRemove[ right[i] ].push_back(i);
    }

    for(int ind = 0;ind<n;ind++)
    {
        if(ind!=0)
        {
            for(int i: toRemove[ind-1])
                T->rem(i);
        }

        for(int i: toAdd[ind])
        {
            if(op[i]==1) T->add(i, Range(height[i], MAXN));//ans = Merge(ans, Range(height[i], MAXN));
            else T->add(i, Range(0, height[i]));//ans = Merge(ans, Range(0, height[i]));
        }

        finalHeight[ind] = T->val.f(0);
    }
}

Compilation message (stderr)

wall.cpp: In function 'Range Merge(Range, Range)':
wall.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

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