oj.uz

Submission #680568

# Submission time Handle Problem Language Result Execution time Memory
680568 2023-01-11T09:09:42 Z nutella Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 4525 ms 76416 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;
using ll = long long;


mt19937 rnd(228);

struct Info {
    ll mx = 0;

    Info() = default;

    explicit Info(ll x) : mx(x) {}
};

Info operator+(Info a, Info b) {
    return Info{max(a.mx, b.mx)};
}

struct Tag {
    ll add = 0;

    Tag() = default;

    explicit Tag(int x) : add(x) {}
};

void apply(Info &a, Tag &b) {
    a.mx += b.add;
}

void apply(Tag &a, Tag &b) {
    a.add += b.add;
}

using key_type = pair<int, int>;

struct Node {
    int y = 0, sz = 0;
    key_type key{};
    Info mine{}, subtree{};
    Tag tag{};

    int L = 0, R = 0;

    Node() = default;

    Node(int prior, key_type key, int siz, Info val) : y(prior), key(key), sz(siz), mine(val), subtree(val) {}
};

void apply(Node &x, Tag &b) {
    apply(x.tag, b);
    apply(x.mine, b);
    apply(x.subtree, b);
}

vector<Node> t{{}};

int create(Node b = Node()) {
    t.emplace_back(b);
    return t.size() - 1;
}

void apply(int x, Tag b) {
    apply(t[x], b);
}

void push(int x) {
    apply(t[x].L, t[x].tag);
    apply(t[x].R, t[x].tag);
    t[x].tag = Tag();
}

void pull(int x) {
    t[x].sz = 1 + t[t[x].L].sz + t[t[x].R].sz;
    t[x].subtree = t[t[x].L].subtree + t[x].mine + t[t[x].R].subtree;
}

int merge(int l, int r) {
    if (!l || !r) return l ^ r;
    push(l), push(r);
    if (t[l].y > t[r].y) {
        t[l].R = merge(t[l].R, r);
        pull(l);
        return l;
    } else {
        t[r].L = merge(l, t[r].L);
        pull(r);
        return r;
    }
}

//key <= k
pair<int, int> split_key(int x, key_type k) {
    if (!x) return {};
    push(x);
    if (t[x].key > k) {
        auto se = split_key(t[x].L, k);
        t[x].L = se.second;
        pull(x);
        return {se.first, x};
    } else {
        auto se = split_key(t[x].R, k);
        t[x].R = se.first;
        pull(x);
        return {x, se.second};
    }
}

//left contains siz
pair<int, int> split_sz(int x, int siz) {
    if (!x) return {};
    push(x);
    if (t[t[x].L].sz >= siz) {
        auto se = split_sz(t[x].L, siz);
        t[x].L = se.second;
        pull(x);
        return {se.first, x};
    } else {
        auto se = split_sz(t[x].R, siz - t[t[x].L].sz - 1);
        t[x].R = se.first;
        pull(x);
        return {x, se.second};
    }
}

void debug_node(int x, string pref = "") {
    if (!x) {
        return;
    }
    pref += "->" + to_string(x);
    debug_node(t[x].L, pref);
    cout << pref << endl;
    debug_node(t[x].R, pref);
}

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
    int Q = X.size(), n = A.size();

    int root = 0;

    auto insert = [&](int i) {
        auto [L, R] = split_key(root, {A[i], i});

        Node now = Node(rnd(), {A[i], i}, 1, Info(i - t[L].sz));

        int x = create(now);

        apply(R, Tag(-1));

        root = merge(L, merge(x, R));
    };

    auto erase = [&](int i) {
        auto [LL, R] = split_key(root, {A[i], i});

        auto [L, trash] = split_sz(LL, t[LL].sz - 1);

        apply(R, Tag(1));

        root = merge(L, R);
    };

    for (int i = 0; i < n; ++i) {
        insert(i);
    }

    std::vector<int> answer(Q);
    for (int j = 0; j < Q; j++) {
        int i = X[j];

        erase(i);
        A[i] = V[j];
        insert(i);

        answer[j] = t[root].subtree.mx;
    }
    return answer;
}

Compilation message

bubblesort2.cpp: In constructor 'Node::Node(int, key_type, int, Info)':
bubblesort2.cpp:42:14: warning: 'Node::key' will be initialized after [-Wreorder]
   42 |     key_type key{};
      |              ^~~
bubblesort2.cpp:41:16: warning:   'int Node::sz' [-Wreorder]
   41 |     int y = 0, sz = 0;
      |                ^~
bubblesort2.cpp:50:5: warning:   when initialized here [-Wreorder]
   50 |     Node(int prior, key_type key, int siz, Info val) : y(prior), key(key), sz(siz), mine(val), subtree(val) {}
      |     ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 7 ms 668 KB Output is correct
4 Correct 8 ms 664 KB Output is correct
5 Correct 8 ms 664 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 8 ms 616 KB Output is correct
8 Correct 7 ms 668 KB Output is correct
9 Correct 7 ms 668 KB Output is correct
10 Correct 7 ms 668 KB Output is correct
11 Correct 7 ms 632 KB Output is correct
12 Correct 7 ms 668 KB Output is correct
13 Correct 7 ms 684 KB Output is correct
14 Correct 7 ms 668 KB Output is correct
15 Correct 7 ms 652 KB Output is correct
16 Correct 7 ms 668 KB Output is correct
17 Correct 7 ms 668 KB Output is correct
18 Correct 7 ms 668 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 7 ms 668 KB Output is correct
4 Correct 8 ms 664 KB Output is correct
5 Correct 8 ms 664 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 8 ms 616 KB Output is correct
8 Correct 7 ms 668 KB Output is correct
9 Correct 7 ms 668 KB Output is correct
10 Correct 7 ms 668 KB Output is correct
11 Correct 7 ms 632 KB Output is correct
12 Correct 7 ms 668 KB Output is correct
13 Correct 7 ms 684 KB Output is correct
14 Correct 7 ms 668 KB Output is correct
15 Correct 7 ms 652 KB Output is correct
16 Correct 7 ms 668 KB Output is correct
17 Correct 7 ms 668 KB Output is correct
18 Correct 7 ms 668 KB Output is correct
19 Correct 29 ms 1360 KB Output is correct
20 Correct 34 ms 1332 KB Output is correct
21 Correct 32 ms 1280 KB Output is correct
22 Correct 36 ms 1384 KB Output is correct
23 Correct 33 ms 1336 KB Output is correct
24 Correct 37 ms 1388 KB Output is correct
25 Correct 31 ms 1388 KB Output is correct
26 Correct 31 ms 1380 KB Output is correct
27 Correct 34 ms 1400 KB Output is correct
28 Correct 30 ms 1360 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2116 KB Output is correct
2 Correct 155 ms 4124 KB Output is correct
3 Correct 259 ms 7740 KB Output is correct
4 Correct 286 ms 7800 KB Output is correct
5 Correct 248 ms 7752 KB Output is correct
6 Correct 249 ms 7856 KB Output is correct
7 Correct 254 ms 7828 KB Output is correct
8 Correct 264 ms 7844 KB Output is correct
9 Correct 253 ms 7756 KB Output is correct
10 Correct 185 ms 7812 KB Output is correct
11 Correct 193 ms 7772 KB Output is correct
12 Correct 170 ms 7788 KB Output is correct
13 Correct 154 ms 7804 KB Output is correct
14 Correct 173 ms 7816 KB Output is correct
15 Correct 158 ms 7744 KB Output is correct
16 Correct 149 ms 7792 KB Output is correct
17 Correct 144 ms 7708 KB Output is correct
18 Correct 152 ms 7712 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 7 ms 668 KB Output is correct
4 Correct 8 ms 664 KB Output is correct
5 Correct 8 ms 664 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 8 ms 616 KB Output is correct
8 Correct 7 ms 668 KB Output is correct
9 Correct 7 ms 668 KB Output is correct
10 Correct 7 ms 668 KB Output is correct
11 Correct 7 ms 632 KB Output is correct
12 Correct 7 ms 668 KB Output is correct
13 Correct 7 ms 684 KB Output is correct
14 Correct 7 ms 668 KB Output is correct
15 Correct 7 ms 652 KB Output is correct
16 Correct 7 ms 668 KB Output is correct
17 Correct 7 ms 668 KB Output is correct
18 Correct 7 ms 668 KB Output is correct
19 Correct 29 ms 1360 KB Output is correct
20 Correct 34 ms 1332 KB Output is correct
21 Correct 32 ms 1280 KB Output is correct
22 Correct 36 ms 1384 KB Output is correct
23 Correct 33 ms 1336 KB Output is correct
24 Correct 37 ms 1388 KB Output is correct
25 Correct 31 ms 1388 KB Output is correct
26 Correct 31 ms 1380 KB Output is correct
27 Correct 34 ms 1400 KB Output is correct
28 Correct 30 ms 1360 KB Output is correct
29 Correct 44 ms 2116 KB Output is correct
30 Correct 155 ms 4124 KB Output is correct
31 Correct 259 ms 7740 KB Output is correct
32 Correct 286 ms 7800 KB Output is correct
33 Correct 248 ms 7752 KB Output is correct
34 Correct 249 ms 7856 KB Output is correct
35 Correct 254 ms 7828 KB Output is correct
36 Correct 264 ms 7844 KB Output is correct
37 Correct 253 ms 7756 KB Output is correct
38 Correct 185 ms 7812 KB Output is correct
39 Correct 193 ms 7772 KB Output is correct
40 Correct 170 ms 7788 KB Output is correct
41 Correct 154 ms 7804 KB Output is correct
42 Correct 173 ms 7816 KB Output is correct
43 Correct 158 ms 7744 KB Output is correct
44 Correct 149 ms 7792 KB Output is correct
45 Correct 144 ms 7708 KB Output is correct
46 Correct 152 ms 7712 KB Output is correct
47 Correct 1020 ms 29000 KB Output is correct
48 Correct 4114 ms 74284 KB Output is correct
49 Correct 4464 ms 76196 KB Output is correct
50 Correct 4519 ms 76060 KB Output is correct
51 Correct 4514 ms 76132 KB Output is correct
52 Correct 4525 ms 76204 KB Output is correct
53 Correct 4273 ms 76076 KB Output is correct
54 Correct 4183 ms 76252 KB Output is correct
55 Correct 4082 ms 76348 KB Output is correct
56 Correct 3931 ms 76264 KB Output is correct
57 Correct 4216 ms 76416 KB Output is correct
58 Correct 3876 ms 76248 KB Output is correct
59 Correct 3690 ms 74956 KB Output is correct
60 Correct 3873 ms 74944 KB Output is correct
61 Correct 3639 ms 74860 KB Output is correct
62 Correct 3734 ms 74804 KB Output is correct
63 Correct 3761 ms 74864 KB Output is correct
64 Correct 3842 ms 74844 KB Output is correct
65 Correct 3603 ms 74720 KB Output is correct
66 Correct 3567 ms 74624 KB Output is correct
67 Correct 3750 ms 74652 KB Output is correct