Lisäykset

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using pii = pair<int,int>;

pii pop(vector<pii>& v) {
    pii p = v.back();
    v.pop_back();
    return p;
}

vector<int> solve(vector<int> X, vector<int> Q) {
    vector<pii> L, R;
    int Lcnt=0, Loff=0;
    auto pushR = [&](pii p) {
        auto [x,cnt] = p;
        if (cnt==0) return;
        if (R.empty() || R.back().first > x) {
            R.emplace_back(x, 0);
        }
        R.back().second += cnt;
    };
    auto popR = [&]() { return pop(R); };
    auto pushL = [&](pii p) {
        auto [x,cnt] = p;
        if (cnt==0) return;
        if (L.empty() || L.back().first+Loff < x) {
            L.emplace_back(x-Loff, 0);
        }
        L.back().second += cnt;
        Lcnt += cnt;
    };
    auto popL = [&]() {
        auto [x,cnt] = pop(L);
        Lcnt -= cnt;
        return pii(x+Loff, cnt);
    };

    for (int i=X.size(); i>0; i--) {
        pushR({X[i-1], 1});
    }
    sort(Q.begin(), Q.end());
    for (int q:Q) {
        while (Lcnt < q) {
            pushL(popR());
        }
        while (Lcnt - L.back().second >= q) {
            pushR(popL());
        }
        int nop = Lcnt - q;
        auto [x,cnt] = popL();
        Loff++;
        pushL({x, nop});
        pushR({x+1, cnt-nop});
    }
    while (!R.empty()) {
        pushL(popR());
    }
    vector<int> ans;
    for (auto [x,cnt] : L) {
        for (int i=0; i<cnt; i++) {
            ans.push_back(x+Loff);
        }
    }
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin>>n>>m;
    vector<int> X(n), Q(m);
    for (int&x:X) cin>>x;
    for (int&q:Q) cin>>q;
    vector<int> ans = solve(X,Q);
    for (int i=0; i<n; i++) {
        cout << ans[i] << " \n"[i+1==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