oj.uz

Submission #517028

# Submission time Handle Problem Language Result Execution time Memory
517028 2022-01-22T11:51:20 Z Jomnoi Wall (IOI14_wall) C++17
100 / 100
 1029 ms 79164 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 7 ms 660 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 9 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 158 ms 8196 KB Output is correct
3 Correct 236 ms 4128 KB Output is correct
4 Correct 655 ms 11744 KB Output is correct
5 Correct 411 ms 12152 KB Output is correct
6 Correct 404 ms 12320 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 8 ms 688 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 7 ms 688 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 131 ms 8528 KB Output is correct
9 Correct 238 ms 4636 KB Output is correct
10 Correct 670 ms 12156 KB Output is correct
11 Correct 407 ms 12100 KB Output is correct
12 Correct 404 ms 12076 KB Output is correct
13 Correct 1 ms 288 KB Output is correct
14 Correct 138 ms 8624 KB Output is correct
15 Correct 39 ms 1804 KB Output is correct
16 Correct 665 ms 12152 KB Output is correct
17 Correct 407 ms 12200 KB Output is correct
18 Correct 408 ms 12156 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 7 ms 672 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 8 ms 680 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 131 ms 8516 KB Output is correct
9 Correct 231 ms 4684 KB Output is correct
10 Correct 661 ms 12148 KB Output is correct
11 Correct 446 ms 12152 KB Output is correct
12 Correct 405 ms 12228 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 129 ms 8516 KB Output is correct
15 Correct 38 ms 1860 KB Output is correct
16 Correct 665 ms 12152 KB Output is correct
17 Correct 404 ms 12156 KB Output is correct
18 Correct 405 ms 12168 KB Output is correct
19 Correct 1012 ms 79068 KB Output is correct
20 Correct 975 ms 79076 KB Output is correct
21 Correct 981 ms 79112 KB Output is correct
22 Correct 971 ms 79072 KB Output is correct
23 Correct 998 ms 79164 KB Output is correct
24 Correct 1029 ms 79072 KB Output is correct
25 Correct 984 ms 79012 KB Output is correct
26 Correct 988 ms 79040 KB Output is correct
27 Correct 973 ms 79112 KB Output is correct
28 Correct 1002 ms 79076 KB Output is correct
29 Correct 994 ms 79068 KB Output is correct
30 Correct 999 ms 78976 KB Output is correct