oj.uz

Submission #466376

# Submission time Handle Problem Language Result Execution time Memory
466376 2021-08-19T04:49:19 Z palilo Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 3580 ms 47340 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
 
template <typename node_t, typename tag_t>
class lazy_segtree {
    // change this (1/2)
    const node_t e = -0x3f3f3f3f;
    const tag_t off {};
    // change this (1/2)
    const size_t n, height, size;
    vector<node_t> tree;
    vector<tag_t> lazy;
 
public:
    lazy_segtree(size_t n) : n(n), height(n ? __lg(n - 1) + 1 : 0), size(1 << height),
                             tree(size << 1, e), lazy(size, off) {}
 
    node_t& operator[](size_t i) { return tree[size + i]; }
    void build() {
        for (size_t i = size; i--;) {
            pull(i);
        }
    }
    void apply(size_t l, size_t r, tag_t f) {
        assert(0 <= l and l <= r and r <= n);
        apply(l, r, f, 0, size, 1);
    }
    node_t prod(size_t l, size_t r) {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, 0, size, 1);
    }
    node_t all_prod() const {
        return tree[1];
    }
 
private:
#define lson (i << 1)
#define rson (i << 1 | 1)
    inline int get_index(node_t& node) const { return &node - tree.data(); }
    inline int get_depth(node_t& node) const { return __lg(get_index(node)); }
    inline int get_height(node_t& node) const { return height - get_depth(node); }
    inline int get_length(node_t& node) const { return 1 << get_height(node); }
    inline int get_first(node_t& node) const {
        int idx = get_index(node);
        int dep = __lg(idx);
        int len = 1 << height - dep;
        return len * (idx ^ 1 << dep);
    }
    void apply(size_t ql, size_t qr, tag_t f, size_t l, size_t r, size_t i) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) {
            all_apply(i, f);
            return;
        }
        if (lazy[i] != off) push(i);
 
        const auto m = (l + r) >> 1;
        apply(ql, qr, f, l, m, lson), apply(ql, qr, f, m, r, rson);
        pull(i);
    }
    node_t prod(size_t ql, size_t qr, size_t l, size_t r, size_t i) {
        if (qr <= l || r <= ql) return e;
        if (ql <= l && r <= qr) return tree[i];
        if (lazy[i] != off) push(i);
 
        const auto m = (l + r) >> 1;
        return op(prod(ql, qr, l, m, lson), prod(ql, qr, m, r, rson));
    }
    void pull(size_t i) {
        tree[i] = op(tree[lson], tree[rson]);
    }
    void push(size_t i) {
        all_apply(lson, lazy[i]);
        all_apply(rson, lazy[i]);
        lazy[i] = off;
    }
    void all_apply(size_t i, tag_t f) {
        mapping(tree[i], f);
        if (i < size) composition(lazy[i], f);
    }
    // change this (2/2)
    node_t op(node_t lhs, node_t rhs) const {
        return max(lhs, rhs);
    }
    void mapping(node_t& node, tag_t f) {
        node += f;
    }
    void composition(tag_t& tag, tag_t f) {
        tag += f;
    }
    // change this (2/2)
#undef lson
#undef rson
};
 
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    constexpr int INF = 0x3f3f3f3f;
    vector<pair<int, int>> vals(a.size() + x.size());
    for (size_t i = 0; i != a.size(); ++i) {
        vals[i] = {a[i], i};
    }
    for (size_t i = 0; i != x.size(); ++i) {
        vals[a.size() + i] = {v[i], x[i]};
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto get_index = [&](pair<int, int> x) {
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    };
    const size_t m = vals.size();
    lazy_segtree<int, int> lazy(m);
    for (size_t i = 0; i != a.size(); ++i) {
        auto id = get_index(pair(a[i], i));
        lazy.apply(id, id + 1, INF + i);
        lazy.apply(id + 1, m, -1);
    }
    vector<int> ret(x.size());
    for (size_t i = 0; i != x.size(); ++i) {
        auto id = get_index(pair(a[x[i]], x[i]));
        lazy.apply(id, id + 1, -(INF + x[i]));
        lazy.apply(id + 1, m, 1);
        a[x[i]] = v[i];
        id = get_index(pair(a[x[i]], x[i]));
        lazy.apply(id, id + 1, INF + x[i]);
        lazy.apply(id + 1, m, -1);
        ret[i] = lazy.all_prod();
    }
    return ret;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 6 ms 356 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 6 ms 472 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 6 ms 388 KB Output is correct
8 Correct 6 ms 432 KB Output is correct
9 Correct 6 ms 460 KB Output is correct
10 Correct 7 ms 460 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 6 ms 436 KB Output is correct
14 Correct 6 ms 464 KB Output is correct
15 Correct 6 ms 428 KB Output is correct
16 Correct 6 ms 460 KB Output is correct
17 Correct 6 ms 460 KB Output is correct
18 Correct 6 ms 460 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 6 ms 356 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 6 ms 472 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 6 ms 388 KB Output is correct
8 Correct 6 ms 432 KB Output is correct
9 Correct 6 ms 460 KB Output is correct
10 Correct 7 ms 460 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 6 ms 436 KB Output is correct
14 Correct 6 ms 464 KB Output is correct
15 Correct 6 ms 428 KB Output is correct
16 Correct 6 ms 460 KB Output is correct
17 Correct 6 ms 460 KB Output is correct
18 Correct 6 ms 460 KB Output is correct
19 Correct 27 ms 924 KB Output is correct
20 Correct 27 ms 972 KB Output is correct
21 Correct 26 ms 960 KB Output is correct
22 Correct 26 ms 972 KB Output is correct
23 Correct 30 ms 988 KB Output is correct
24 Correct 29 ms 980 KB Output is correct
25 Correct 27 ms 972 KB Output is correct
26 Correct 26 ms 984 KB Output is correct
27 Correct 27 ms 972 KB Output is correct
28 Correct 25 ms 976 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1228 KB Output is correct
2 Correct 122 ms 2584 KB Output is correct
3 Correct 232 ms 4468 KB Output is correct
4 Correct 224 ms 4560 KB Output is correct
5 Correct 224 ms 4568 KB Output is correct
6 Correct 216 ms 4568 KB Output is correct
7 Correct 216 ms 4500 KB Output is correct
8 Correct 228 ms 4572 KB Output is correct
9 Correct 242 ms 4504 KB Output is correct
10 Correct 170 ms 3808 KB Output is correct
11 Correct 190 ms 3944 KB Output is correct
12 Correct 188 ms 3780 KB Output is correct
13 Correct 181 ms 3800 KB Output is correct
14 Correct 188 ms 3832 KB Output is correct
15 Correct 192 ms 3868 KB Output is correct
16 Correct 168 ms 3856 KB Output is correct
17 Correct 211 ms 3788 KB Output is correct
18 Correct 187 ms 3800 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 6 ms 356 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 6 ms 472 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 6 ms 388 KB Output is correct
8 Correct 6 ms 432 KB Output is correct
9 Correct 6 ms 460 KB Output is correct
10 Correct 7 ms 460 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 6 ms 436 KB Output is correct
14 Correct 6 ms 464 KB Output is correct
15 Correct 6 ms 428 KB Output is correct
16 Correct 6 ms 460 KB Output is correct
17 Correct 6 ms 460 KB Output is correct
18 Correct 6 ms 460 KB Output is correct
19 Correct 27 ms 924 KB Output is correct
20 Correct 27 ms 972 KB Output is correct
21 Correct 26 ms 960 KB Output is correct
22 Correct 26 ms 972 KB Output is correct
23 Correct 30 ms 988 KB Output is correct
24 Correct 29 ms 980 KB Output is correct
25 Correct 27 ms 972 KB Output is correct
26 Correct 26 ms 984 KB Output is correct
27 Correct 27 ms 972 KB Output is correct
28 Correct 25 ms 976 KB Output is correct
29 Correct 39 ms 1228 KB Output is correct
30 Correct 122 ms 2584 KB Output is correct
31 Correct 232 ms 4468 KB Output is correct
32 Correct 224 ms 4560 KB Output is correct
33 Correct 224 ms 4568 KB Output is correct
34 Correct 216 ms 4568 KB Output is correct
35 Correct 216 ms 4500 KB Output is correct
36 Correct 228 ms 4572 KB Output is correct
37 Correct 242 ms 4504 KB Output is correct
38 Correct 170 ms 3808 KB Output is correct
39 Correct 190 ms 3944 KB Output is correct
40 Correct 188 ms 3780 KB Output is correct
41 Correct 181 ms 3800 KB Output is correct
42 Correct 188 ms 3832 KB Output is correct
43 Correct 192 ms 3868 KB Output is correct
44 Correct 168 ms 3856 KB Output is correct
45 Correct 211 ms 3788 KB Output is correct
46 Correct 187 ms 3800 KB Output is correct
47 Correct 898 ms 16448 KB Output is correct
48 Correct 3312 ms 44484 KB Output is correct
49 Correct 3580 ms 47044 KB Output is correct
50 Correct 3377 ms 47040 KB Output is correct
51 Correct 3446 ms 47040 KB Output is correct
52 Correct 3378 ms 47044 KB Output is correct
53 Correct 3306 ms 47168 KB Output is correct
54 Correct 3042 ms 47340 KB Output is correct
55 Correct 3184 ms 47240 KB Output is correct
56 Correct 3090 ms 47324 KB Output is correct
57 Correct 3276 ms 47276 KB Output is correct
58 Correct 3164 ms 47188 KB Output is correct
59 Correct 3089 ms 45856 KB Output is correct
60 Correct 3051 ms 45916 KB Output is correct
61 Correct 3096 ms 45880 KB Output is correct
62 Correct 2863 ms 45788 KB Output is correct
63 Correct 2863 ms 45720 KB Output is correct
64 Correct 2793 ms 45764 KB Output is correct
65 Correct 2667 ms 45568 KB Output is correct
66 Correct 2749 ms 45628 KB Output is correct
67 Correct 2822 ms 45708 KB Output is correct