Lisäykset

#include <bits/stdc++.h>

constexpr auto MAXN = 1000000;
std::vector<int64_t> T(4 * MAXN);

void add(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        return;
    }
    if (l == tl && r == tr) {
        ++T[v];
    } else {
        const auto tm = (tl + tr) / 2;
        add(v * 2, tl, tm, l, std::min(r, tm));
        add(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r);
    }
}

int64_t query(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return T[v];
    }
    const auto tm = (tl + tr) / 2;
    return T[v] + (pos <= tm ? query(v * 2, tl, tm, pos) : query(v * 2 + 1, tm + 1, tr, pos));
}

void add(int r) {
    add(1, 0, MAXN, 0, r);
}

int64_t query(int pos) {
    return query(1, 0, MAXN, pos);
}

int64_t value(int64_t v) {
    return v + query(v);
}

struct R {
    int64_t v;
    int64_t c;
    int64_t b;

    bool operator<(const R& other) const {
        return b + c < other.b + other.c;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    std::cin >> n >> m;

    std::set<R> RS = [n]() {
        std::set<R> RS;
        std::vector<R> tmp;
        for (auto i = 0; i < n; ++i) {
            int64_t x;
            std::cin >> x;
            if (tmp.empty()) {
                tmp.push_back({x, 1, 0});
            }
            else if (auto& r = tmp.back(); r.v == x) {
                ++r.c;
            }
            else {
                tmp.push_back({x, 1, r.b + r.c});
            }
        }
        for (auto&& r : tmp) {
            RS.insert(std::move(r));
        }
        return RS;
    }();

    for (auto i = 0; i < m; ++i) {
        int64_t k;
        std::cin >> k;

        auto ri = RS.lower_bound({0, k, 0});
        auto r = *ri;
        const auto v = value(r.v);
        const auto mv = k - r.b;
        const auto st = r.c - mv;
        const auto rb = r.b;

        auto rpi = ri != RS.begin() ? std::prev(ri) : RS.end();
        auto rni = std::next(ri);
        RS.erase(ri);
        if (st > 0 && rpi != RS.end() && v - 1 == value(rpi->v)) {
            auto rp = *rpi;
            rp.c += st;
            r.c -= st;
            r.b += st;
            RS.erase(rpi);
            RS.insert(rp);
        }
        if (rni != RS.end() && v + 1 == value(rni->v)) {
            auto rn = *rni;
            r.c -= mv;
            rn.c += mv;
            rn.b -= mv;
            RS.erase(rni);
            RS.insert(rn);
        } else {
            auto rn = R{r.v + 1, mv, rb + st};
            r.c -= mv;
            RS.insert(rn);
        }
        if (r.c > 0) {
            RS.insert(r);
        }
        add(r.v - 1);
    }
    for (const auto& r : RS) {
        const auto vl = value(r.v);
        for (auto i = 0; i < r.c; ++i) {
            std::cout << vl << ' ';
        }
    }
    std::cout << '\n';
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 3

Verdict: ACCEPTED

Test 4

Group: 1, 3

Verdict: ACCEPTED

Test 5

Group: 1, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED