oj.uz

Submission #517024

# Submission time Handle Problem Language Result Execution time Memory
517024 2022-01-22T11:31:38 Z Jomnoi Wall (IOI14_wall) C++17
0 / 100
 2748 ms 27812 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 4 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 137 ms 8608 KB Output is correct
3 Correct 783 ms 7528 KB Output is correct
4 Incorrect 2748 ms 27812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 2 ms 300 KB Output is correct
3 Incorrect 4 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Incorrect 4 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -