Lisäykset

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    map<int, pair<int, int>> p;
    int lst = -1;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x != lst) p[i] = {x, 0};
        lst = x;
    }
    p[n] = {1e9, 0};
    auto mergeck = [&](auto it1) {
        auto it2 = next(it1);
        if (it1->second.first + it1->second.second == it2->second.first) {
            it1->second.second += it2->second.second;
            p.erase(it2);
        }
    };
    auto print = [&]() {
        lst = n;
        int add = 0;
        int res[n];
        for (auto [pos, d] : views::reverse(p)) {
            add += d.second;
            for (int i = pos; i < lst; ++i) res[i] = d.first + add;
            lst = pos;
        }
        for (int i = 0; i < n; ++i) cout << res[i] << " ";
        cout << endl;
    };
    for (int i = 0; i < m; ++i) {
        int k;
        cin >> k;
        if (!k) continue;
        k--;
        auto it2 = p.upper_bound(k);
        auto it1 = prev(it2);
        if (it2->first != k+1) {
            int amt = k-it1->first+1;
            assert(amt > 0);
            int pos = it2->first - amt;
            assert(pos != it1->first);
            auto cp = it1->second;
            auto ins = p.insert(it2, {pos, {cp.first+cp.second+1, 0}});
            mergeck(ins);
            if (it1 == p.begin()) continue;
            it1 = prev(it1);
        }
        it1->second.second++;
        mergeck(it1);
    }
    print();
}

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