oj.uz

Submission #1016659

# Submission time Handle Problem Language Result Execution time Memory
1016659 2024-07-08T10:07:31 Z NValchanov Wall (IOI14_wall) C++17
0 / 100
 173 ms 217424 KB 
#include <bits/stdc++.h>
#include "wall.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;
        }

        friend node operator+(node Lnode, node Rnode)
        {
            node result;

            result.lazy = INF;
            result.minel = min(Lnode.minel, Rnode.minel);
            result.maxel = max(Lnode.maxel, Rnode.maxel);

            return result;
        }
    };

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

    SegmentTree()
    {
        n = 0;
    }

    SegmentTree(int _n)
    {
        n = _n;
    }

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

        tree[idx] = node(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] = tree[2 * idx] + tree[2 * idx + 1];
    }

    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] = tree[2 * idx] + tree[2 * idx + 1];
    }

    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
            update_min(left, right, val);
    }

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

SegmentTree st;

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

    for(int i = 0; i < q; 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);
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 203828 KB Output is correct
2 Correct 86 ms 203864 KB Output is correct
3 Incorrect 90 ms 204112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 203920 KB Output is correct
2 Correct 173 ms 217424 KB Output is correct
3 Incorrect 129 ms 211096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 203864 KB Output is correct
2 Correct 85 ms 203856 KB Output is correct
3 Incorrect 83 ms 203996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 203768 KB Output is correct
2 Correct 87 ms 203892 KB Output is correct
3 Incorrect 83 ms 203856 KB Output isn't correct
4 Halted 0 ms 0 KB -