Submission #517028

#	Time	Username	Problem	Language	Result	Execution time	Memory
517028		Jomnoi	Wall (IOI14_wall)	C++17	100 / 100	1029 ms	79164 KiB

wall

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int INF = 1e9 + 7;

class Block {
    public :
        int low, high;
        Block() : low(0), high(INF) {}
};

class SegmentTree {
    protected :
        const int N;
        vector <Block> tree;
    public :
        SegmentTree(const int &n) : N(n) {
            tree.resize(4 * n, Block());
        }

        void push(const int &idx, const int &l, const int &r) {
            if(l == r) {
                return;
            }

            push_lazy(idx * 2, 1, tree[idx].low);
            push_lazy(idx * 2, 2, tree[idx].high);
            push_lazy(idx * 2 + 1, 1, tree[idx].low);
            push_lazy(idx * 2 + 1, 2, tree[idx].high);
            tree[idx] = Block();
        }
        
        void push_lazy(int idx, const int &op, const int &h) {
            if(op == 1) {
                tree[idx].low = max(tree[idx].low, h);
                tree[idx].high = max(tree[idx].high, tree[idx].low);
            }
            else {
                tree[idx].high = min(tree[idx].high, h);
                tree[idx].low = min(tree[idx].low, tree[idx].high);
            }
        }

        void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const int &op, const int &h) {
            if(r < ql or qr < l) {
                return;
            }
            if(ql <= l and r <= qr) {
                push_lazy(idx, op, h);
                return;
            }
            
            push(idx, l, r);
            int mid = (l + r) / 2;
            update(idx * 2, l, mid, ql, qr, op, h);
            update(idx * 2 + 1, mid + 1, r, ql, qr, op, h);
        }

        void answer(const int &idx, const int &l, const int &r, int arr[]) {
            if(l == r) {
                arr[l] = tree[idx].low;
                return;
            }

            push(idx, l, r);
            int mid = (l + r) / 2;
            answer(idx * 2, l, mid, arr);
            answer(idx * 2 + 1, mid + 1, r, arr);
        }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegmentTree st(n);
    for(int i = 0; i < k; i++) {
        st.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }

    st.answer(1, 0, n - 1, finalHeight);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39