oj.uz

Submission #538364

# Submission time Handle Problem Language Result Execution time Memory
538364 2022-03-16T16:32:06 Z timreizin Wall (IOI14_wall) C++17
100 / 100
 1658 ms 151740 KB 
#include "wall.h"
#include <vector>

using namespace std;

struct SegTree
{
    int n;
    vector<pair<int, int>> tree;
    vector<pair<int, int>> mod;

    SegTree(int _n) : n(_n)
    {
        tree.resize(4 * n + 5, {0, 1e5});
        mod.resize(4 * n + 5, {0, 1e5});
    }

    void push(int v)
    {
        tree[v << 1].first = max(tree[v << 1].first, mod[v].first);
        tree[v << 1].second = max(tree[v << 1].second, mod[v].first);
        tree[v << 1 | 1].first = max(tree[v << 1 | 1].first, mod[v].first);
        tree[v << 1 | 1].second = max(tree[v << 1 | 1].second, mod[v].first);
        tree[v << 1].first = min(tree[v << 1].first, mod[v].second);
        tree[v << 1].second = min(tree[v << 1].second, mod[v].second);
        tree[v << 1 | 1].first = min(tree[v << 1 | 1].first, mod[v].second);
        tree[v << 1 | 1].second = min(tree[v << 1 | 1].second, mod[v].second);
        mod[v << 1].first = max(mod[v << 1].first, mod[v].first);
        mod[v << 1].second = max(mod[v << 1].second, mod[v].first);
        mod[v << 1 | 1].first = max(mod[v << 1 | 1].first, mod[v].first);
        mod[v << 1 | 1].second = max(mod[v << 1 | 1].second, mod[v].first);
        mod[v << 1].first = min(mod[v << 1].first, mod[v].second);
        mod[v << 1].second = min(mod[v << 1].second, mod[v].second);
        mod[v << 1 | 1].first = min(mod[v << 1 | 1].first, mod[v].second);
        mod[v << 1 | 1].second = min(mod[v << 1 | 1].second, mod[v].second);
        mod[v] = {0, 1e5};
    }

    void updateMax(int a, int b, int val, int v, int l, int r)
    {
        if (a > r || b < l) return;
        if (a == l && b == r)
        {
            //make >= val
            tree[v].first = max(tree[v].first, val);
            tree[v].second = max(tree[v].second, val);
            mod[v].first = max(mod[v].first, val);
            mod[v].second = max(mod[v].second, val);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        updateMax(a, min(b, m), val, v << 1, l, m);
        updateMax(max(a, m + 1), b, val, v << 1 | 1, m + 1, r);
    }

    void updateMax(int a, int b, int val)
    {
        updateMax(a, b, val, 1, 0, n - 1);
    }

    void updateMin(int a, int b, int val, int v, int l, int r)
    {
        if (a > r || b < l) return;
        if (a == l && b == r)
        {
            //make <= val
            tree[v].first = min(tree[v].first, val);
            tree[v].second = min(tree[v].second, val);
            mod[v].first = min(mod[v].first, val);
            mod[v].second = min(mod[v].second, val);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        updateMin(a, min(b, m), val, v << 1, l, m);
        updateMin(max(a, m + 1), b, val, v << 1 | 1, m + 1, r);
    }

    void updateMin(int a, int b, int val)
    {
        updateMin(a, b, val, 1, 0, n - 1);
    }

    pair<int, int> get(int p, int v, int l, int r)
    {
        if (l == r) return tree[v];
        push(v);
        int m = (l + r) >> 1;
        if (p <= m) return get(p, v << 1, l, m);
        return get(p, v << 1 | 1, m + 1, r);
    }

    int get(int p)
    {
        auto [l, r] = get(p, 1, 0, n - 1);
        return l;
    }

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree st(n);
    for (int i = 0; i < k; ++i)
    {
        if (op[i] == 1) st.updateMax(left[i], right[i], height[i]);
        else st.updateMin(left[i], right[i], height[i]);
    }
    for (int i = 0; i < n; ++i) finalHeight[i] = st.get(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 304 KB Output is correct
4 Correct 11 ms 1124 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 8 ms 1068 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 148 ms 13816 KB Output is correct
3 Correct 228 ms 8520 KB Output is correct
4 Correct 687 ms 24352 KB Output is correct
5 Correct 391 ms 24820 KB Output is correct
6 Correct 423 ms 23364 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 424 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1108 KB Output is correct
5 Correct 7 ms 1108 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 148 ms 13900 KB Output is correct
9 Correct 233 ms 8524 KB Output is correct
10 Correct 641 ms 24268 KB Output is correct
11 Correct 449 ms 24840 KB Output is correct
12 Correct 399 ms 23304 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 149 ms 13888 KB Output is correct
15 Correct 41 ms 2528 KB Output is correct
16 Correct 728 ms 24376 KB Output is correct
17 Correct 383 ms 23768 KB Output is correct
18 Correct 443 ms 23804 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 2 ms 340 KB Output is correct
4 Correct 8 ms 1012 KB Output is correct
5 Correct 8 ms 1124 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 150 ms 13868 KB Output is correct
9 Correct 249 ms 8524 KB Output is correct
10 Correct 643 ms 24400 KB Output is correct
11 Correct 399 ms 25048 KB Output is correct
12 Correct 403 ms 23356 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 152 ms 13956 KB Output is correct
15 Correct 38 ms 2436 KB Output is correct
16 Correct 725 ms 24372 KB Output is correct
17 Correct 413 ms 23800 KB Output is correct
18 Correct 399 ms 23732 KB Output is correct
19 Correct 1607 ms 151572 KB Output is correct
20 Correct 1533 ms 151508 KB Output is correct
21 Correct 1557 ms 151628 KB Output is correct
22 Correct 1552 ms 151644 KB Output is correct
23 Correct 1603 ms 151576 KB Output is correct
24 Correct 1553 ms 151536 KB Output is correct
25 Correct 1582 ms 151572 KB Output is correct
26 Correct 1583 ms 151604 KB Output is correct
27 Correct 1592 ms 151560 KB Output is correct
28 Correct 1658 ms 151672 KB Output is correct
29 Correct 1638 ms 151736 KB Output is correct
30 Correct 1575 ms 151740 KB Output is correct