Submission #680568

#	Time	Username	Problem	Language	Result	Execution time	Memory
680568		nutella	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4525 ms	76416 KiB

bubblesort2

#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 (stderr)

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 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40