oj.uz

Submission #680674

# Submission time Handle Problem Language Result Execution time Memory
680674 2023-01-11T13:46:47 Z borisAngelov Wall (IOI14_wall) C++17
100 / 100
 956 ms 99368 KB 
#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)
{
    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].maxv, 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 828 KB Output is correct
5 Correct 7 ms 824 KB Output is correct
6 Correct 7 ms 828 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 121 ms 8116 KB Output is correct
3 Correct 128 ms 4180 KB Output is correct
4 Correct 401 ms 21464 KB Output is correct
5 Correct 248 ms 22444 KB Output is correct
6 Correct 256 ms 20824 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 5 ms 764 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 158 ms 13936 KB Output is correct
9 Correct 138 ms 7984 KB Output is correct
10 Correct 433 ms 21384 KB Output is correct
11 Correct 246 ms 22488 KB Output is correct
12 Correct 307 ms 20900 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 125 ms 13920 KB Output is correct
15 Correct 23 ms 2028 KB Output is correct
16 Correct 376 ms 21684 KB Output is correct
17 Correct 250 ms 21288 KB Output is correct
18 Correct 243 ms 21124 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 7 ms 852 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 160 ms 13892 KB Output is correct
9 Correct 125 ms 7960 KB Output is correct
10 Correct 370 ms 21368 KB Output is correct
11 Correct 268 ms 22448 KB Output is correct
12 Correct 247 ms 20836 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 180 ms 13840 KB Output is correct
15 Correct 25 ms 1996 KB Output is correct
16 Correct 363 ms 21644 KB Output is correct
17 Correct 297 ms 21068 KB Output is correct
18 Correct 245 ms 21120 KB Output is correct
19 Correct 867 ms 99228 KB Output is correct
20 Correct 855 ms 96932 KB Output is correct
21 Correct 862 ms 99236 KB Output is correct
22 Correct 854 ms 96768 KB Output is correct
23 Correct 827 ms 96772 KB Output is correct
24 Correct 837 ms 96760 KB Output is correct
25 Correct 849 ms 96924 KB Output is correct
26 Correct 906 ms 99368 KB Output is correct
27 Correct 956 ms 99280 KB Output is correct
28 Correct 911 ms 96684 KB Output is correct
29 Correct 852 ms 96804 KB Output is correct
30 Correct 812 ms 96792 KB Output is correct