Submission #680673

#	Time	Username	Problem	Language	Result	Execution time	Memory
680673		borisAngelov	Wall (IOI14_wall)	C++17	0 / 100	148 ms	13900 KiB

wall

#include <iostream>
#include "wall.h"

using namespace std;

const int maxn = 2000005;
const int inf = 1000000000;

struct state
{
    int minv;
    int maxv;
};

state tree[4 * maxn];

void push_lazy(int node, int l, int r)
{
    if (l != r)
    {
        int left_child = (node << 1);

        tree[left_child].minv = min(tree[node].maxv, max(tree[left_child].minv, tree[node].minv));
        tree[left_child].maxv = max(tree[node].minv, min(tree[left_child].maxv, tree[node].maxv));

        int right_child = ((node << 1) | 1);

        tree[right_child].minv = min(tree[node].minv, max(tree[right_child].minv, tree[node].minv));
        tree[right_child].maxv = max(tree[node].minv, min(tree[right_child].maxv, tree[node].maxv));
    }

    tree[node].minv = 0;
    tree[node].maxv = inf;
}

void update(int node, int l, int r, int ql, int qr, int type, int val)
{
    if (l > qr || r < ql)
    {
        return;
    }

    if (ql <= l && r <= qr)
    {
        if (type == 1)
        {
            tree[node].minv = max(tree[node].minv, val);
            tree[node].maxv = max(tree[node].maxv, val);
        }
        else
        {
            tree[node].minv = min(tree[node].minv, val);
            tree[node].maxv = min(tree[node].maxv, val);
        }

        return;
    }

    push_lazy(node, l, r);

    int mid = (l + r) >> 1;

    update((node << 1), l, mid, ql, qr, type, val);
    update(((node << 1) | 1), mid + 1, r, ql, qr, type, val);
}

int query(int node, int l, int r, int idx)
{
    if (l == r)
    {
        return tree[node].minv;
    }

    push_lazy(node, l, r);

    int mid = (l + r) >> 1;

    if (idx <= mid) return query((node << 1), l, mid, idx);
    return query(((node << 1) | 1), mid + 1, r, idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int final_height[])
{
    for (int i = 1; i <= 4 * n; ++i)
    {
        tree[i].minv = 0;
        tree[i].maxv = inf;
    }

    for (int i = 0; i < k; ++i)
    {
        update(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        final_height[i - 1] = query(1, 1, n, i);
    }
}

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