oj.uz

Submission #830863

# Submission time Handle Problem Language Result Execution time Memory
830863 2023-08-19T11:56:55 Z wortelworm Wall (IOI14_wall) C++17
100 / 100
 757 ms 92500 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 {
                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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 74060 KB Output is correct
2 Correct 51 ms 74164 KB Output is correct
3 Correct 52 ms 74188 KB Output is correct
4 Correct 56 ms 74168 KB Output is correct
5 Correct 56 ms 74256 KB Output is correct
6 Correct 56 ms 74208 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 74116 KB Output is correct
2 Correct 261 ms 81912 KB Output is correct
3 Correct 282 ms 77428 KB Output is correct
4 Correct 690 ms 82044 KB Output is correct
5 Correct 313 ms 81960 KB Output is correct
6 Correct 306 ms 82000 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 74096 KB Output is correct
2 Correct 52 ms 74136 KB Output is correct
3 Correct 55 ms 74188 KB Output is correct
4 Correct 64 ms 74320 KB Output is correct
5 Correct 56 ms 74288 KB Output is correct
6 Correct 55 ms 74244 KB Output is correct
7 Correct 50 ms 74068 KB Output is correct
8 Correct 263 ms 87724 KB Output is correct
9 Correct 273 ms 81356 KB Output is correct
10 Correct 694 ms 91568 KB Output is correct
11 Correct 312 ms 92108 KB Output is correct
12 Correct 336 ms 90536 KB Output is correct
13 Correct 57 ms 74108 KB Output is correct
14 Correct 272 ms 87756 KB Output is correct
15 Correct 80 ms 75156 KB Output is correct
16 Correct 649 ms 91596 KB Output is correct
17 Correct 315 ms 90948 KB Output is correct
18 Correct 338 ms 91172 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 74052 KB Output is correct
2 Correct 48 ms 74196 KB Output is correct
3 Correct 56 ms 74204 KB Output is correct
4 Correct 52 ms 74240 KB Output is correct
5 Correct 50 ms 74240 KB Output is correct
6 Correct 51 ms 74252 KB Output is correct
7 Correct 47 ms 74176 KB Output is correct
8 Correct 259 ms 87740 KB Output is correct
9 Correct 266 ms 81220 KB Output is correct
10 Correct 745 ms 91568 KB Output is correct
11 Correct 334 ms 92072 KB Output is correct
12 Correct 309 ms 90532 KB Output is correct
13 Correct 56 ms 74112 KB Output is correct
14 Correct 264 ms 87772 KB Output is correct
15 Correct 80 ms 75172 KB Output is correct
16 Correct 611 ms 91592 KB Output is correct
17 Correct 321 ms 91040 KB Output is correct
18 Correct 327 ms 91108 KB Output is correct
19 Correct 720 ms 92436 KB Output is correct
20 Correct 701 ms 92368 KB Output is correct
21 Correct 723 ms 92464 KB Output is correct
22 Correct 708 ms 92492 KB Output is correct
23 Correct 702 ms 92340 KB Output is correct
24 Correct 723 ms 92352 KB Output is correct
25 Correct 702 ms 92420 KB Output is correct
26 Correct 728 ms 92428 KB Output is correct
27 Correct 712 ms 92368 KB Output is correct
28 Correct 690 ms 92500 KB Output is correct
29 Correct 757 ms 92380 KB Output is correct
30 Correct 699 ms 92464 KB Output is correct