Submission #830861

#	Time	Username	Problem	Language	Result	Execution time	Memory
830861		wortelworm	Wall (IOI14_wall)	C++17	24 / 100	619 ms	82076 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = INT32_MAX;
const int tree_size = 1 << 21;
// const int tree_size = 16;

struct node {
    int value, minimum, maximum;
};

// value, min/add, max/remove
vector<node> tree;

/// assumes only one of value and (min/add and/or max/remove) is set
/// resets the min and max to default values by propagating to value or children
void propagate(int index) {
    if (index >= tree_size) {
        // bottom layer
        if (tree[index].value < tree[index].minimum) {
            tree[index].value = tree[index].minimum;
        }
        if (tree[index].value > tree[index].maximum) {
            tree[index].value = tree[index].maximum;
        }
    } else {
        // non-bottom layer
        for (int child : {2*index, 2*index+1}) {
            if (tree[index].value >= 0) {
                // set value
                tree[child] = {tree[index].value, 0, INF};
                continue;
            }

            if (tree[index].minimum > 0) {
                // propagate minimum
                if (tree[child].maximum < tree[index].minimum) {

                    tree[child] = {tree[index].minimum, 0, INF};

                } else if (tree[child].value > 0 && tree[child].value < tree[index].minimum) {

                    tree[child] = {tree[index].minimum, 0, INF};

                } else if (tree[child].minimum < tree[index].minimum) {

                    tree[child].minimum = tree[index].minimum;
                }
            }

            if (tree[index].maximum < INF) {
                // propagate maximum
                if (tree[child].minimum > tree[index].maximum) {

                    tree[child] = {tree[index].maximum, 0, INF};

                } else if (tree[child].value > 0 && tree[child].value > tree[index].maximum) {

                    tree[child] = {tree[index].maximum, 0, INF};

                } else if (tree[child].maximum > tree[index].maximum) {

                    tree[child].maximum = tree[index].maximum;
                }
            }
        }
        tree[index].value = -1;
    }
    tree[index].minimum = 0;
    tree[index].maximum = INF;
}

// overall (begin, end),  index, current (begin, end),  type, value
void do_operation(int a, int b, int type, int value, int index = 1, int x = 0, int y = tree_size-1) {
    if (b < x || y < a) {
        return;
    }

    propagate(index);

    if (a <= x && y <= b) {
        // if this is the bottom layer, tree[index].first may already be non-zero
        if (type == 1) {
            // adding
            if (tree[index].value > 0) {
                if (tree[index].value < value) {
                    tree[index].value = value;
                }
            } else {
                tree[index].minimum = max(tree[index].minimum, value);
            }
        } else {
            // removing
            if (tree[index].value > 0) {
                if (tree[index].value > value) {
                    tree[index].value = value;
                }
            } else {
                tree[index].maximum = min(tree[index].maximum, value);
            }
        }
        // propagate(index);
        return;
    }

    int mid = (x+y)/2;
    do_operation(a, b, type, value, 2*index, x, mid);
    do_operation(a, b, type, value, 2*index+1, mid+1, y);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    
    // tree.resize(2*tree_size, {0, 0, INF});
    tree.resize(tree_size, {-1, 0, INF});
    tree.resize(2*tree_size, {0, 0, INF});

    for (int i = 0; i < k; i++)
    {
        int a = left[i];
        int b = right[i];

        int type = op[i];
        int value = height[i];

        do_operation(a, b, type, value);
    }

    for (int i = 0; i < 2*tree_size; i++)
    {
        propagate(i);
    }

    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = tree[tree_size+i].value;
    }
}

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