Lisäykset

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

typedef long long ll;

int diff[101010];
set<int> ch;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int prev = -1;
    int smallest = 0;
    for (int i=1; i<=n; ++i){
        int a;
        cin >> a;
        if (i==1) smallest = a;
        else{
            diff[i] = a - prev;
            if (a != prev) ch.insert(i);
        }
        prev = a;
    }
    ch.insert(n+1); // To avoid that it == ch.end() below.
    for (int i=1; i<=m; ++i){
        
        int k;
        cin >> k;
        auto it = ch.upper_bound(k);
        if (*it == k+1){
            diff[k+1]--;
            if (diff[k+1]==0){
                if (*it <= n) ch.erase(*it); // If so that we don't erase n+1.
            }
            smallest++;
        }
        else {
            auto ite = ch.begin();
            int b;
            int next = *it;
            if (*ite != *it) {
                smallest++;
                it--;
                b = k - *it + 1;
                diff[*it]--;
                if (diff[*it]==0 && *it <= n) ch.erase(*it);
            }
            else{
                b = k;    
            }
            diff[next]--;
            diff[next - b]=1;
            if (diff[next]==0 && next <= n) ch.erase(next);
            ch.insert(next-b);
        }
        /*
        cout << "here " << i << " " << k << " " << smallest << "\n";
        for (int j=1; j<=n; ++j) cout << diff[j] << " ";
        cout << "\n";
        for (auto u:ch) cout << u << " ";
        cout << "\n";
        */
    }
    int curr = smallest;
    for (int i=1; i<=n; ++i){
        curr+=diff[i];
        cout << curr << " ";
    }
    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