oj.uz

Submission #1098042

# Submission time Handle Problem Language Result Execution time Memory
1098042 2024-10-08T23:04:33 Z orcslop Wall (IOI14_wall) C++17
100 / 100
 671 ms 151752 KB 
#include <bits/stdc++.h>
using namespace std;
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int inf = 1e9; 

struct Data {
    int mn = 0, mx = inf; 
}; 

/**
 * T = tree node type, which wiint be long long
 * We use the Query struct to manage updates.
 */
template <class T> class LazySegtree {
  private:
    const int sz;
    vector<Data> tree;      // tree[i] = sum of this node's range
    vector<Data> lazy;  // lazy[i] = lazy update for the range

    /** @return result of joining two tree nodes together */

    /** applies lazy update to t[v], places update at lz[v] */
    void apply(int v, const Data &x) {
        ckmax(tree[v].mn, x.mn); 
        ckmax(tree[v].mx, tree[v].mn); 
        ckmin(tree[v].mx, x.mx); 
        ckmin(tree[v].mn, tree[v].mx); 
    }

    /** pushes down lazy update to children of v */
    void push_down(int v) {
        apply(2 * v, tree[v]);
        apply(2 * v + 1, tree[v]);
        tree[v] = Data(); 
    }

    void range_update(int v, int l, int r, int ql, int qr, const Data &x) {
        if (qr < l || ql > r) { return; }
        if (ql <= l && r <= qr) {
            apply(v, x);
        } else {
            push_down(v);
            int m = (l + r) / 2;
            range_update(2 * v, l, m, ql, qr, x);
            range_update(2 * v + 1, m + 1, r, ql, qr, x);
        }
    }

    Data get(int v, int pos, int l, int r) {
        if (l == r) { return tree[v]; }
        push_down(v);
        int m = (l + r) / 2;
        if(pos <= m) return get(2 * v, pos, l, m); 
        else return get(2 * v + 1, pos, m + 1, r); 
    }

  public:
    LazySegtree(int n) : sz(n), tree(4 * sz), lazy(4 * sz) {
        
    }

    /** updates [ql, qr] with the update x */
    void range_update(int ql, int qr, const Data &x) {
        range_update(1, 0, sz - 1, ql, qr, x);
    }

    /** sum of array values on [ql, qr] */
    Data get(int pos) { return get(1, pos, 0, sz - 1); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int final_height[]) {
    LazySegtree<int> st(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            st.range_update(left[i], right[i], {height[i], inf});
        } else {
            st.range_update(left[i], right[i], {0, height[i]});
        }
    }
    for (int i = 0; i < n; i++) { 
        Data c = st.get(i); 
        if(c.mn <= height[i] && height[i] <= c.mx){
            final_height[i] = height[i]; 
        }
        final_height[i] = c.mn; 
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 89 ms 13908 KB Output is correct
3 Correct 135 ms 8548 KB Output is correct
4 Correct 412 ms 24408 KB Output is correct
5 Correct 183 ms 24912 KB Output is correct
6 Correct 173 ms 23380 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 81 ms 13940 KB Output is correct
9 Correct 132 ms 8528 KB Output is correct
10 Correct 375 ms 24400 KB Output is correct
11 Correct 186 ms 24840 KB Output is correct
12 Correct 172 ms 23348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 115 ms 13900 KB Output is correct
15 Correct 23 ms 2396 KB Output is correct
16 Correct 425 ms 24404 KB Output is correct
17 Correct 196 ms 23888 KB Output is correct
18 Correct 183 ms 23872 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1284 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 13936 KB Output is correct
9 Correct 137 ms 8472 KB Output is correct
10 Correct 376 ms 24392 KB Output is correct
11 Correct 196 ms 25172 KB Output is correct
12 Correct 170 ms 23284 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 87 ms 13840 KB Output is correct
15 Correct 23 ms 2396 KB Output is correct
16 Correct 423 ms 24460 KB Output is correct
17 Correct 240 ms 23888 KB Output is correct
18 Correct 182 ms 23764 KB Output is correct
19 Correct 628 ms 151632 KB Output is correct
20 Correct 600 ms 151752 KB Output is correct
21 Correct 671 ms 151632 KB Output is correct
22 Correct 669 ms 151632 KB Output is correct
23 Correct 668 ms 151696 KB Output is correct
24 Correct 652 ms 151636 KB Output is correct
25 Correct 643 ms 151632 KB Output is correct
26 Correct 663 ms 151632 KB Output is correct
27 Correct 604 ms 151624 KB Output is correct
28 Correct 632 ms 151716 KB Output is correct
29 Correct 606 ms 151636 KB Output is correct
30 Correct 635 ms 151616 KB Output is correct