Lisäykset

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

const int N=2<<17;
int stree[2*N];
int x[N];

void inc(int a, int b, int n) {
    a+=N;
    while (a>0) {
        stree[a]++;
        a/=2;
    }
    if (b==n) return;
    b+=N+1;
    while (b>0) {
        stree[b]--;
        b/=2;
    }
}

int get(int ind) {
    int a=N;
    ind+=N;
    int su=0;
    while (a<=ind) {
        if (a%2==1) su+=stree[a++];
        if (ind%2==0) su+=stree[ind--];
        a/=2;
        ind/=2;
    }
    return su;
}

pair<int,int> trange(int val, int n) {
    int nod=1;
    while (stree[nod]>val) nod*=2;
    int val1=val-stree[nod];
    int up=nod+1;
    if (nod==1) {
        up=n+N+1;
    } else {
        while (up<N) {
            if (stree[2*up]<=val1) {
                val1-=stree[2*up];
                up=2*up+1;
            } else {
                up=2*up;
            }
        }
    }
    while (nod < N && stree[nod]==val) nod*=2;
    int val2=val-stree[nod];
    int dow=nod+1;
    while (dow<N) {
        if (stree[2*dow]< val2) {
            val2-=stree[2*dow];
            dow=2*dow+1;
        } else {
            dow*=2;
        }
    }

    return {dow-N,up-N-1};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>x[i];
        stree[i+N]=x[i]-x[i-1];
    }
    for (int i=N-1;i>0;i--) stree[i]=stree[2*i]+stree[2*i+1];
    for (int i=0;i<m;i++) {
        int k;
        cin>>k;
        int val = get(k);
        pair<int,int> xx = trange(val,n);
        inc(1,xx.F-1,n);
        inc(xx.S-(k-xx.F),xx.S,n);
    }
    for (int i=1;i<=n;i++) cout<<get(i)<<" ";
    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