oj.uz

Submission #1016695

# Submission time Handle Problem Language Result Execution time Memory
1016695 2024-07-08T10:33:05 Z NValchanov Wall (IOI14_wall) C++17
100 / 100
 470 ms 138576 KB 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 2e6 + 10;
const int MAXQ = 5e5 + 10;
const int MAXH = 1e5 + 10;
const int INF = 1e9 + 10;

struct SegmentTree
{
    struct node
    {
        int lazy;
        int minel;
        int maxel;

        node()
        {
            lazy = INF;
            minel = 0;
            maxel = 0;
        }
        node(int x)
        {
            minel = maxel = x;
        }
    };

    node tree[4 * MAXN];
    int h[MAXN];
    int n;

    SegmentTree()
    {
        n = 0;
    }

    void push_lazy(int left, int right, int idx)
    {
        if(tree[idx].lazy == INF)
            return;

        tree[idx].minel = tree[idx].maxel = tree[idx].lazy;

        if(left != right)
        {
            tree[2 * idx].lazy = tree[2 * idx + 1].lazy = tree[idx].lazy;
        }

        tree[idx].lazy = INF;
    }

    void update_max(int left, int right, int idx, int qleft, int qright, int val)
    {
        push_lazy(left, right, idx);

        if(qright < left || right < qleft)
            return;

        if(tree[idx].minel >= val)
            return;

        if(qleft <= left && right <= qright && tree[idx].maxel <= val)
        {
            tree[idx].lazy = val;
            push_lazy(left, right, idx);
            return;
        }

        int mid = left + (right - left) / 2;

        update_max(left, mid, 2 * idx, qleft, qright, val);
        update_max(mid + 1, right, 2 * idx + 1, qleft, qright, val);

        tree[idx].minel = min(tree[2 * idx].minel, tree[2 * idx + 1].minel);
        tree[idx].maxel = max(tree[2 * idx].maxel, tree[2 * idx + 1].maxel);
    }

    void update_min(int left, int right, int idx, int qleft, int qright, int val)
    {
        push_lazy(left, right, idx);

        if(qright < left || right < qleft)
            return;

        if(tree[idx].maxel <= val)
            return;

        if(qleft <= left && right <= qright && tree[idx].minel >= val)
        {
            tree[idx].lazy = val;
            push_lazy(left, right, idx);
            return;
        }

        int mid = left + (right - left) / 2;

        update_min(left, mid, 2 * idx, qleft, qright, val);
        update_min(mid + 1, right, 2 * idx + 1, qleft, qright, val);

        tree[idx].minel = min(tree[2 * idx].minel, tree[2 * idx + 1].minel);
        tree[idx].maxel = max(tree[2 * idx].maxel, tree[2 * idx + 1].maxel);
    }

    void build(int left, int right, int idx)
    {
        push_lazy(left, right, idx);

        if(left == right)
        {
            h[left] = tree[idx].minel;
            return;
        }

        int mid = left + (right - left) / 2;

        build(left, mid, 2 * idx);
        build(mid + 1, right, 2 * idx + 1);
    }

    void update_max(int left, int right, int val)
    {
        update_max(1, n, 1, left, right, val);
    }

    void update_min(int left, int right, int val)
    {
        update_min(1, n, 1, left, right, val);
    }

    void build()
    {
        build(1, n, 1);
    }

    void query(int type, int left, int right, int val)
    {
        if(type == 1)
            update_max(left, right, val);
        else if(type == 2)
            update_min(left, right, val);
        else
            assert(false);
    }

    int access(int idx)
    {
        return h[idx + 1];
    }
};

SegmentTree st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    st.n = n;

    for(int i = 0; i < k; i++)
    {
        st.query(op[i], left[i] + 1, right[i] + 1, height[i]);
    }

    st.build();

    for(int i = 0; i < n; i++)
    {
        finalHeight[i] = st.access(i);
    }
}

// int op[MAXN];
// int l[MAXN];
// int r[MAXN];
// int height[MAXN];
// int finalHeight[MAXN];
// int n, k;

// int main()
// {
//     cin >> n >> k;

//     for(int i = 0; i < k; i++)
//     {
//         cin >> op[i] >> l[i] >> r[i] >> height[i];
//     }

//     buildWall(n, k, op, l, r, height, finalHeight);

//     for(int i = 0; i < n; i++)
//     {
//         cout << finalHeight[i] << " ";
//     }
//     cout << endl;

//     return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 94300 KB Output is correct
2 Correct 20 ms 94404 KB Output is correct
3 Correct 25 ms 94300 KB Output is correct
4 Correct 20 ms 94576 KB Output is correct
5 Correct 19 ms 94484 KB Output is correct
6 Correct 19 ms 94556 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 94372 KB Output is correct
2 Correct 91 ms 102100 KB Output is correct
3 Correct 62 ms 97616 KB Output is correct
4 Correct 148 ms 105332 KB Output is correct
5 Correct 156 ms 103584 KB Output is correct
6 Correct 135 ms 103504 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 94132 KB Output is correct
2 Correct 16 ms 94300 KB Output is correct
3 Correct 15 ms 94300 KB Output is correct
4 Correct 17 ms 94556 KB Output is correct
5 Correct 17 ms 94552 KB Output is correct
6 Correct 17 ms 94556 KB Output is correct
7 Correct 19 ms 94300 KB Output is correct
8 Correct 104 ms 103252 KB Output is correct
9 Correct 68 ms 98384 KB Output is correct
10 Correct 132 ms 105304 KB Output is correct
11 Correct 125 ms 103644 KB Output is correct
12 Correct 187 ms 103484 KB Output is correct
13 Correct 16 ms 94300 KB Output is correct
14 Correct 103 ms 101972 KB Output is correct
15 Correct 36 ms 95056 KB Output is correct
16 Correct 355 ms 112976 KB Output is correct
17 Correct 227 ms 112320 KB Output is correct
18 Correct 223 ms 112472 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 94296 KB Output is correct
2 Correct 15 ms 94296 KB Output is correct
3 Correct 16 ms 94300 KB Output is correct
4 Correct 20 ms 94412 KB Output is correct
5 Correct 18 ms 94556 KB Output is correct
6 Correct 18 ms 94356 KB Output is correct
7 Correct 15 ms 94176 KB Output is correct
8 Correct 121 ms 103384 KB Output is correct
9 Correct 63 ms 98388 KB Output is correct
10 Correct 131 ms 105412 KB Output is correct
11 Correct 125 ms 103656 KB Output is correct
12 Correct 136 ms 103592 KB Output is correct
13 Correct 15 ms 94300 KB Output is correct
14 Correct 96 ms 101968 KB Output is correct
15 Correct 32 ms 95064 KB Output is correct
16 Correct 332 ms 112980 KB Output is correct
17 Correct 205 ms 112464 KB Output is correct
18 Correct 201 ms 112300 KB Output is correct
19 Correct 448 ms 138536 KB Output is correct
20 Correct 447 ms 136016 KB Output is correct
21 Correct 444 ms 138576 KB Output is correct
22 Correct 444 ms 136024 KB Output is correct
23 Correct 470 ms 136076 KB Output is correct
24 Correct 459 ms 136016 KB Output is correct
25 Correct 449 ms 136020 KB Output is correct
26 Correct 446 ms 138364 KB Output is correct
27 Correct 439 ms 138412 KB Output is correct
28 Correct 458 ms 135980 KB Output is correct
29 Correct 448 ms 136024 KB Output is correct
30 Correct 451 ms 135892 KB Output is correct