Submission #517024

#	Time	Username	Problem	Language	Result	Execution time	Memory
517024		Jomnoi	Wall (IOI14_wall)	C++17	0 / 100	2748 ms	27812 KiB

wall

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

class Block {
    public :
        int val;
        vector <pair <int, int>> lazy;
        Block() : val(), lazy() {}
};

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

        void add(const int &recieve, vector <pair <int, int>> vec) {
            for(auto &v : vec) {
                if(v.first == 1) {
                    tree[recieve].lazy.clear();
                }
                else {
                    while(!tree[recieve].lazy.empty() and tree[recieve].lazy.back().first == 2) {
                        v.second = min(v.second, tree[recieve].lazy.back().second);
                        tree[recieve].lazy.pop_back();
                    }
                }
                tree[recieve].lazy.push_back(v);
            }
        }

        void push_lazy(const int &idx, const int &l, const int &r) {
            if(tree[idx].lazy.empty()) {
                return;
            }

            if(l != r) {
                add(idx * 2, tree[idx].lazy);
                add(idx * 2 + 1, tree[idx].lazy);
            }
            for(auto [op, h] : tree[idx].lazy) {
                if(op == 1) {
                    tree[idx].val = max(tree[idx].val, h);
                }
                else {
                    tree[idx].val = min(tree[idx].val, h);
                }
            }

            tree[idx].lazy.clear();
        }

        void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const int &op, const int &h) {
            push_lazy(idx, l, r);
            if(r < ql or qr < l) {
                return;
            }
            if(ql <= l and r <= qr) {
                add(idx, vector <pair <int, int>> {make_pair(op, h)});
                push_lazy(idx, l, r);
                return;
            }
            
            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[]) {
            push_lazy(idx, l, r);
            if(l == r) {
                arr[l] = tree[idx].val;
                return;
            }

            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);

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

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