oj.uz

Submission #830859

# Submission time Handle Problem Language Result Execution time Memory
830859 2023-08-19T11:54:11 Z wortelworm Wall (IOI14_wall) C++17
24 / 100
 598 ms 82000 KB 
#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 {
                if (tree[index].maximum < 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 {
                if (tree[index].minimum > value) {
                    tree[index].value = value;
                } else {
                tree[index].maximum = max(tree[index].maximum, value);
                }
            }
            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.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 74156 KB Output is correct
2 Correct 49 ms 74180 KB Output is correct
3 Correct 54 ms 74120 KB Output is correct
4 Correct 53 ms 74244 KB Output is correct
5 Correct 63 ms 74188 KB Output is correct
6 Incorrect 52 ms 74176 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 74172 KB Output is correct
2 Correct 232 ms 81900 KB Output is correct
3 Correct 245 ms 77452 KB Output is correct
4 Correct 598 ms 82000 KB Output is correct
5 Correct 278 ms 82000 KB Output is correct
6 Correct 276 ms 81968 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74140 KB Output is correct
2 Correct 48 ms 74164 KB Output is correct
3 Correct 60 ms 74112 KB Output is correct
4 Correct 53 ms 74276 KB Output is correct
5 Correct 51 ms 74224 KB Output is correct
6 Incorrect 51 ms 74248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 74104 KB Output is correct
2 Correct 50 ms 74240 KB Output is correct
3 Correct 51 ms 74140 KB Output is correct
4 Correct 53 ms 74188 KB Output is correct
5 Correct 51 ms 74164 KB Output is correct
6 Incorrect 52 ms 74292 KB Output isn't correct
7 Halted 0 ms 0 KB -