Submission #773747

#	Time	Username	Problem	Language	Result	Execution time	Memory
773747		boris_mihov	Wall (IOI14_wall)	C++17	100 / 100	613 ms	130724 KiB

wall

#include "wall.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 2000000 + 10;
const int INF  = 1e9;

int n, q;
struct SegmentTree
{
    struct Node
    {
        int min;
        int max;
        int lazy;

        Node()
        {
            min = max = 0;
            lazy = -1;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        Node res;
        res.min = std::min(left.min, right.min);
        res.max = std::max(left.max, right.max);
        return res;
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == -1)
        {
            return;
        }

        tree[node].min = tree[node].lazy;
        tree[node].max = tree[node].lazy;
    
        if (l < r)
        {
            tree[2*node].lazy = tree[node].lazy;
            tree[2*node + 1].lazy = tree[node].lazy;
        }

        tree[node].lazy = -1;
    }

    void updateMAX(int l, int r, int node, int queryL, int queryR, int val)
    {
        push(node, l, r);
        if (r < queryL || queryR < l || tree[node].min >= val)
        {
            return;
        }

        if (queryL <= l && r <= queryR && tree[node].max <= val)
        {
            tree[node].lazy = val;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        updateMAX(l, mid, 2*node, queryL, queryR, val);
        updateMAX(mid + 1, r, 2*node + 1, queryL, queryR, val);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void updateMIN(int l, int r, int node, int queryL, int queryR, int val)
    {
        push(node, l, r);
        if (r < queryL || queryR < l || tree[node].max <= val)
        {
            return;
        }

        if (queryL <= l && r <= queryR && tree[node].min >= val)
        {
            tree[node].lazy = val;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        updateMIN(l, mid, 2*node, queryL, queryR, val);
        updateMIN(mid + 1, r, 2*node + 1, queryL, queryR, val);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void assignANS(int l, int r, int node, int to[])
    {
        push(node, l, r);
        if (l == r)
        {
            to[l - 1] = tree[node].min;
            return;
        }

        int mid = (l + r) / 2;
        assignANS(l, mid, 2*node, to);
        assignANS(mid + 1, r, 2*node + 1, to);
    }

    void updateMIN(int l, int r, int val)
    {
        updateMIN(1, n, 1, l, r, val);
    }

    void updateMAX(int l, int r, int val)
    {
        updateMAX(1, n, 1, l, r, val);
    }

    void assignANS(int to[])
    {
        assignANS(1, n, 1, to);
    }
};

SegmentTree tree;
void buildWall(int N, int Q, int op[], int left[], int right[], int height[], int finalHeight[])
{
    n = N;
    q = Q;

    for (int i = 0 ; i < q ; ++i)
    {
        if (op[i] == 1)
        {
            tree.updateMAX(left[i] + 1, right[i] + 1, height[i]);
        } else
        {
            tree.updateMIN(left[i] + 1, right[i] + 1, height[i]);
        }
    }

    tree.assignANS(finalHeight);
    return;
}

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