Lisäykset

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

const int N=1<<17;
int st[2*N];

void add(int a, int b, int v){
	a+=N;
	b+=N;
	while (a<=b){
		if (a%2){
			st[a++]+=v;
		}
		if (!(b%2)){
			st[b--]+=v;
		}
		a/=2;
		b/=2;
	}
}

int get(int i, int n){
	if (i<=0) return -1;
	if (i>n) return 1e9;
	int s=0;
	for (i+=N;i;i/=2){
		s+=st[i];
	}
	return s;
}

int where(int x, int n){
	int mi=-1;
	int ma=n+1;
	while (mi<=ma){
		int mid=(mi+ma)/2;
		if (get(mid,n)<x){
			mi=mid+1;
		} else {
			ma=mid-1;
		}
	}
	return mi;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		int x;
		cin>>x;
		add(i,i,x);
	}
	for (int i=0;i<m;i++){
		int k;
		cin>>k;

		int t=get(k,n);
		int a=where(t,n);
		int b=where(t+1,n)-1;
		add(1, a-1, 1);
		add(b-(k-a), b, 1);
	}
	for (int i=1;i<=n;i++){
		cout<<get(i,n)<<" ";
	}
	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