oj.uz

Submission #1086964

# Submission time Handle Problem Language Result Execution time Memory
1086964 2024-09-12T00:24:53 Z eysbutno Wall (IOI14_wall) C++17
100 / 100
 790 ms 89168 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int INF = 2e9;
class Segtree {
    struct Update {
        int min_val = 0;
        int max_val = INF;
    };
    const int sz;
    vector<Update> t;

    void apply(int v, const Update &x) {
        t[v].min_val = max(t[v].min_val, x.min_val);
        t[v].max_val = max(t[v].max_val, t[v].min_val);
        t[v].max_val = min(t[v].max_val, x.max_val);
        t[v].min_val = min(t[v].min_val, t[v].max_val);
    }

    void pushdown(int v) {
        apply(2 * v, t[v]);
        apply(2 * v + 1, t[v]);
        t[v] = Update();
    }

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

    Update qry(int v, int l, int r, int idx) {
        if (l == r) {
            return t[v];
        } else {
            pushdown(v);
            int m = (l + r) / 2;
            return (idx <= m) ? qry(2 * v, l, m, idx)
                              : qry(2 * v + 1, m + 1, r, idx);
        }
    }

  public:
    Segtree(int n) : sz(n) {
        t.assign(4 * n, Update());
    }

    void upd(int ql, int qr, const Update &x) {
        upd(1, 0, sz - 1, ql, qr, x);
    }

    Update get(int idx) {
        return qry(1, 0, sz - 1, idx);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int res[]) {
    Segtree st(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            st.upd(left[i], right[i], {height[i], INF});
        } else {
            st.upd(left[i], right[i], {-INF, height[i]});
        }
    }
    for (int i = 0; i < n; i++) {
        res[i] = st.get(i).min_val;
    }
}

Subtask #1
8.0 / 8.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 860 KB Output is correct
5 Correct 4 ms 900 KB Output is correct
6 Correct 4 ms 860 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 98 ms 13884 KB Output is correct
3 Correct 110 ms 8016 KB Output is correct
4 Correct 339 ms 21328 KB Output is correct
5 Correct 207 ms 21768 KB Output is correct
6 Correct 196 ms 20308 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 2 ms 348 KB Output is correct
4 Correct 4 ms 956 KB Output is correct
5 Correct 4 ms 892 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13904 KB Output is correct
9 Correct 110 ms 8016 KB Output is correct
10 Correct 343 ms 21200 KB Output is correct
11 Correct 206 ms 21908 KB Output is correct
12 Correct 193 ms 20244 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 91 ms 13908 KB Output is correct
15 Correct 23 ms 1880 KB Output is correct
16 Correct 320 ms 21180 KB Output is correct
17 Correct 204 ms 20644 KB Output is correct
18 Correct 219 ms 20564 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 2 ms 600 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 5 ms 960 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 13904 KB Output is correct
9 Correct 120 ms 8016 KB Output is correct
10 Correct 375 ms 21312 KB Output is correct
11 Correct 207 ms 21844 KB Output is correct
12 Correct 193 ms 20304 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 113 ms 13904 KB Output is correct
15 Correct 20 ms 1884 KB Output is correct
16 Correct 329 ms 21328 KB Output is correct
17 Correct 201 ms 20740 KB Output is correct
18 Correct 198 ms 20568 KB Output is correct
19 Correct 744 ms 88916 KB Output is correct
20 Correct 736 ms 88912 KB Output is correct
21 Correct 741 ms 89084 KB Output is correct
22 Correct 731 ms 89168 KB Output is correct
23 Correct 726 ms 88912 KB Output is correct
24 Correct 748 ms 89028 KB Output is correct
25 Correct 739 ms 88952 KB Output is correct
26 Correct 757 ms 88912 KB Output is correct
27 Correct 773 ms 88916 KB Output is correct
28 Correct 783 ms 88916 KB Output is correct
29 Correct 790 ms 88912 KB Output is correct
30 Correct 746 ms 89004 KB Output is correct