oj.uz

Submission #1098040

# Submission time Handle Problem Language Result Execution time Memory
1098040 2024-10-08T22:59:07 Z orcslop Wall (IOI14_wall) C++17
61 / 100
 442 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

const ll inf = 1e18; 

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

/**
 * T = tree node type, which will 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<ll> 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 1884 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 87 ms 14044 KB Output is correct
3 Correct 135 ms 9808 KB Output is correct
4 Correct 395 ms 30696 KB Output is correct
5 Correct 191 ms 31316 KB Output is correct
6 Correct 178 ms 29520 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1884 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 4 ms 1908 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 14004 KB Output is correct
9 Correct 131 ms 9744 KB Output is correct
10 Correct 399 ms 30544 KB Output is correct
11 Correct 183 ms 31312 KB Output is correct
12 Correct 173 ms 29672 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 84 ms 14064 KB Output is correct
15 Correct 24 ms 3664 KB Output is correct
16 Correct 425 ms 30532 KB Output is correct
17 Correct 186 ms 30032 KB Output is correct
18 Correct 197 ms 29956 KB Output is correct

Subtask #4
0 / 39.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 6 ms 1884 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 80 ms 14032 KB Output is correct
9 Correct 134 ms 9804 KB Output is correct
10 Correct 393 ms 30772 KB Output is correct
11 Correct 185 ms 31316 KB Output is correct
12 Correct 176 ms 29700 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 14068 KB Output is correct
15 Correct 27 ms 3668 KB Output is correct
16 Correct 425 ms 30604 KB Output is correct
17 Correct 189 ms 30032 KB Output is correct
18 Correct 183 ms 30036 KB Output is correct
19 Runtime error 442 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -