oj.uz

Submission #519073

# Submission time Handle Problem Language Result Execution time Memory
519073 2022-01-25T15:00:51 Z tabr Wall (IOI14_wall) C++17
100 / 100
 1108 ms 59304 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifndef tabr
#include "wall.h"
#endif

const int inf = (int) 1e9;

struct segtree {
    using T = int;
    using F = pair<int, int>;
    int n;
    int size;
    int log_size;
    vector<T> node;
    vector<F> lazy;

    T e() {
        return 0;
    }

    F id() {
        return make_pair(-inf, inf);
    }

    T op(T a, T b) {
        return min(a, b);
    }

    T mapping(F f, T x) {
        x = max(x, f.first);
        x = min(x, f.second);
        return x;
    }

    F composition(F f, F g) {
        if (f.first == f.second) {
            return f;
        }
        if (g.first == g.second) {
            if (g.first < f.first) {
                return make_pair(f.first, f.first);
            }
            if (f.second < g.second) {
                return make_pair(f.second, f.second);
            }
            return g;
        }
        if (f.first > g.second) {
            return make_pair(f.first, f.first);
        }
        if (f.second < g.first) {
            return make_pair(f.second, f.second);
        }
        return make_pair(max(f.first, g.first), min(f.second, g.second));
    }

    segtree() : segtree(0) {}
    segtree(int _n) {
        build(vector<T>(_n, e()));
    }
    segtree(const vector<T>& v) {
        build(v);
    }

    void build(const vector<T>& v) {
        n = (int) v.size();
        if (n <= 1) {
            log_size = 0;
        } else {
            log_size = 32 - __builtin_clz(n - 1);
        }
        size = 1 << log_size;
        node.resize(2 * size, e());
        lazy.resize(size, id());
        for (int i = 0; i < n; i++) {
            node[i + size] = v[i];
        }
        for (int i = size - 1; i > 0; i--) {
            pull(i);
        }
    }

    void push(int x) {
        node[2 * x] = mapping(lazy[x], node[2 * x]);
        node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]);
        if (2 * x < size) {
            lazy[2 * x] = composition(lazy[x], lazy[2 * x]);
            lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]);
        }
        lazy[x] = id();
    }

    void pull(int x) {
        node[x] = op(node[2 * x], node[2 * x + 1]);
    }

    void set(int p, T v) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        node[p] = v;
        for (int i = 1; i <= log_size; i++) {
            pull(p >> i);
        }
    }

    T get(int p) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        return node[p];
    }

    T get(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        for (int i = log_size; i >= 1; i--) {
            if (((l >> i) << i) != l) {
                push(l >> i);
            }
            if (((r >> i) << i) != r) {
                push((r - 1) >> i);
            }
        }
        T vl = e();
        T vr = e();
        while (l < r) {
            if (l & 1) {
                vl = op(vl, node[l++]);
            }
            if (r & 1) {
                vr = op(node[--r], vr);
            }
            l >>= 1;
            r >>= 1;
        }
        return op(vl, vr);
    }

    void apply(int p, F f) {
        assert(0 <= p && p < n);
        p += size;
        for (int i = log_size; i >= 1; i--) {
            push(p >> i);
        }
        node[p] = mapping(f, node[p]);
        for (int i = 1; i <= log_size; i++) {
            pull(p >> i);
        }
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        for (int i = log_size; i >= 1; i--) {
            if (((l >> i) << i) != l) {
                push(l >> i);
            }
            if (((r >> i) << i) != r) {
                push((r - 1) >> i);
            }
        }
        int ll = l;
        int rr = r;
        while (l < r) {
            if (l & 1) {
                node[l] = mapping(f, node[l]);
                if (l < size) {
                    lazy[l] = composition(f, lazy[l]);
                }
                l++;
            }
            if (r & 1) {
                r--;
                node[r] = mapping(f, node[r]);
                if (l < size) {
                    lazy[r] = composition(f, lazy[r]);
                }
            }
            l >>= 1;
            r >>= 1;
        }
        l = ll;
        r = rr;
        for (int i = 1; i <= log_size; i++) {
            if (((l >> i) << i) != l) {
                pull(l >> i);
            }
            if (((r >> i) << i) != r) {
                pull((r - 1) >> i);
            }
        }
    }
};

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int res[]) {
    segtree seg(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            seg.apply(l[i], r[i] + 1, make_pair(h[i], inf));
        } else {
            seg.apply(l[i], r[i] + 1, make_pair(-inf, h[i]));
        }
    }
    for (int i = 0; i < n; i++) {
        res[i] = seg.get(i);
    }
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 10;
    int k = 6;
    int op[] = {1, 2, 2, 1, 1, 2};
    int l[] = {1, 4, 3, 0, 2, 6};
    int r[] = {8, 9, 6, 5, 2, 7};
    int h[] = {4, 1, 5, 3, 5, 0};
    int res[100] = {};
    buildWall(n, k, op, l, r, h, res);
    for (int i = 0; i < n; i++) {
        cout << res[i] << " \n"[i == n - 1];
    }
    return 0;
}
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 10 ms 716 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 7 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 123 ms 8112 KB Output is correct
3 Correct 165 ms 7972 KB Output is correct
4 Correct 444 ms 20216 KB Output is correct
5 Correct 397 ms 20740 KB Output is correct
6 Correct 364 ms 19172 KB Output is correct

Subtask #3
29.0 / 29.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 332 KB Output is correct
4 Correct 7 ms 708 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 127 ms 14004 KB Output is correct
9 Correct 158 ms 7984 KB Output is correct
10 Correct 455 ms 20192 KB Output is correct
11 Correct 368 ms 20744 KB Output is correct
12 Correct 379 ms 19068 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 146 ms 13828 KB Output is correct
15 Correct 39 ms 1980 KB Output is correct
16 Correct 506 ms 20192 KB Output is correct
17 Correct 378 ms 19620 KB Output is correct
18 Correct 386 ms 19596 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 348 KB Output is correct
4 Correct 7 ms 804 KB Output is correct
5 Correct 6 ms 812 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 268 KB Output is correct
8 Correct 136 ms 13872 KB Output is correct
9 Correct 176 ms 8036 KB Output is correct
10 Correct 459 ms 20216 KB Output is correct
11 Correct 375 ms 20668 KB Output is correct
12 Correct 364 ms 19180 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 136 ms 14068 KB Output is correct
15 Correct 32 ms 1868 KB Output is correct
16 Correct 470 ms 20192 KB Output is correct
17 Correct 366 ms 19524 KB Output is correct
18 Correct 378 ms 19616 KB Output is correct
19 Correct 1044 ms 59240 KB Output is correct
20 Correct 1069 ms 59244 KB Output is correct
21 Correct 1086 ms 59304 KB Output is correct
22 Correct 1030 ms 59296 KB Output is correct
23 Correct 1041 ms 59168 KB Output is correct
24 Correct 1030 ms 59148 KB Output is correct
25 Correct 1037 ms 59236 KB Output is correct
26 Correct 1108 ms 59236 KB Output is correct
27 Correct 1049 ms 59220 KB Output is correct
28 Correct 1029 ms 59204 KB Output is correct
29 Correct 1020 ms 59204 KB Output is correct
30 Correct 1059 ms 59244 KB Output is correct