Submission #1166114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166114		martin_nedev	Wall (IOI14_wall)	C++20	0 / 100	103 ms	70708 KiB

wall

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

#ifdef __LOCAL__
    #include "grader.cpp"
#endif // __LOCAL__

#include "wall.h"

const int INF = 1e9;
const int MAXN = 2e6 + 5;
class SegmentTree
{
private:
    struct Node
    {
        int Min, Max;
        Node()
        {
            Min = INF;
            Max = -INF;
        }

        Node(int Min, int Max)
            :Min(Min), Max(Max){}

        bool operator== (const Node &other)
        {
            return (this->Min == other.Min)&&(this->Max == other.Max);
        }
    };

    int N;
    Node lazy[4*MAXN];

    void UpdateLazy(int type, int value, int node)
    {
        if (type == 1) // Max
        {
            lazy[node].Min = max(lazy[node].Min, value);
            lazy[node].Max = max(lazy[node].Max, value);
        }

        if (type == 2) // Min
        {
            lazy[node].Min = min(lazy[node].Min, value);
            lazy[node].Max = min(lazy[node].Max, value);
        }
    }
    void PushdownLazy(int node)
    {
        UpdateLazy(1, lazy[node].Max, 2*node);
        UpdateLazy(2, lazy[node].Min, 2*node);

        UpdateLazy(1, lazy[node].Max, 2*node+1);
        UpdateLazy(2, lazy[node].Min, 2*node+1);

        lazy[node] = Node();
    }
    void UpdateInternal(int type, int queryL, int queryR, int value, int node, int l, int r)
    {
        if (l > queryR || r < queryL)
            return;

        if (queryL <= l && r <= queryR)
        {
            UpdateLazy(type, value, node);
            return;
        }

        PushdownLazy(node);

        UpdateInternal(type, queryL, queryR, value, 2*node, l, (l+r)/2);
        UpdateInternal(type, queryL, queryR, value, 2*node+1, (l+r)/2+1, r);
    }

    void AnswerInternal(int finalHeight[], int node, int l, int r)
    {
        if (l == r)
        {
            if (lazy[node].Min > lazy[node].Max)
                swap(lazy[node].Min, lazy[node].Max);

            if (abs(lazy[node].Min) == INF)
            {
                finalHeight[l] = 0;
            }

            else
            {
                finalHeight[l] = lazy[node].Min;
            }

            return;
        }

        PushdownLazy(node);

        AnswerInternal(finalHeight, 2*node, l, (l+r)/2);
        AnswerInternal(finalHeight, 2*node+1, (l+r)/2+1, r);
    }

public:
    SegmentTree(){}
    SegmentTree(int n)
    {
        N = n;
    }
    void Update(int type, int queryL, int queryR, int value)
    {
        UpdateInternal(type, queryL, queryR, value, 1, 0, N-1);
    }

    void Answer(int finalHeight[])
    {
        AnswerInternal(finalHeight, 1, 0, N-1);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegmentTree *tree = new SegmentTree(n);

    for (int i = 0; i < n; i++)
    {
        tree->Update(op[i], left[i], right[i], height[i]);
    }

    tree->Answer(finalHeight);

    return;
}

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