Submission #61566376

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a[500005], s[500005], ft[2000005];
void update(int x, int v) {
    while (x <= n){
        ft[x] += v;
        x += x & -x;
    }
}
int query(int x){
    int res = 0;
    while (x){
        res += ft[x];
        x -= x & -x;
    }
    return res;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int n, a[500005], s[500005], ft[2000005];

void update(int x, int v) {
    while (x <= n){
        ft[x] += v;
        x += x & -x;
    }
}

int query(int x){
    int res = 0;
    while (x){
        res += ft[x];
        x -= x & -x;
    }
    return res;
}


int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];

    s[1] = a[1];
    int r1 = s[1] + 1;
    update(r1, 1);
    int cnt = 1;

    for (int i = 2; i <= n; i++) {
        int z = cnt - query(i - 1);
        s[i] = a[i] + z;
        int ri = s[i] + i;
        update(ri, 1);
        cnt++;
    }

    for (int i = 1; i <= n; i++) {
        int lost = n - i, bi = s[i] - lost;
        if (bi < 0) bi = 0;
        cout << bi << ' ';
    }
}

Submission Info

Judge Result