Lisäykset

#include <bits/stdc++.h>

using namespace std;

#define N (1<<17)

int v[2 * N];

void vset(int k, int x) {
    k += N;
    v[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        v[k] = v[2 * k] + v[2 * k + 1];
    }
}

void inc(int k, int x) {
    k += N;
    v[k] += x;
    for (k /= 2; k >= 1; k /= 2) {
        v[k] = v[2 * k] + v[2 * k + 1];
    }
}

int sum(int a, int b) {
    a += N;
    b += N;
    int s = 0;
    while (a <= b) {
        if (a % 2 == 1) s += v[a++];
        if (b % 2 == 0) s += v[b--];
        a /= 2;
        b /= 2;
    }
    return s;
}

int findk(int i, int k, int c) {
    if (i >= N) return i - N;
    if (c + v[2 * i] >= k) return findk(2 * i, k, c);
    return findk(2 * i + 1, k, c + v[2 * i]);
}

int main () {
    int n, m;
    cin>>n>>m;
    int prev = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        vset(i, x - prev);
        prev = x;
    }
    vset(n, 1000001);
    for (int i = 0; i < m; i++) {
        int k;
        cin>>k;
        int x = sum(0, k - 1);
        //cout<<"x "<<x<<endl;
        int j = findk(1, x, 0);
        //cout<<"j "<<j<<endl;
        int jj = findk(1, x + 1, 0);
        //cout<<"jj "<<jj<<endl;
        inc(0, 1);
        inc(j, -1);
        inc(jj - k + j, 1);
        inc(jj, -1);
        
    }
    for (int i = 0; i < n; i++) {
        cout<<sum(0, i)<<" ";
    }
    cout<<endl;
}

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