Submission #1433620

---

Source Code Expand

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long LL;

const int maxn = 1000009;
int a[maxn], x[maxn];
LL s1[maxn], s2[maxn], pre, res;
int n, m, cnt, last;

inline int read(){
	char ch = getchar(); int x = 0;
	while (ch < '0' || '9' < ch) ch = getchar();
	while ('0' <= ch && ch <= '9') { x = x*10 + ch-'0'; ch = getchar(); }
	return x;
}

int del(){
	int m = 0;
	for (int i=1; i<=n; i++)
		if (i == 1 || x[i] != x[m]) x[++m] = x[i];
	return m;
}

int search(int k){
	int l = 1, r = m, mid;
	while (l < r){
		mid = (l+r) >> 1;
		if (k <= x[mid]) r = mid;
		else l = mid+1;
	}
	return l;
}

void update(LL s[], int x, int y){
	for (; x<=m; x+=lowbit(x)) s[x] += y;
}

LL query(LL s[], int x){
	LL res = 0; for (; x; x-=lowbit(x)) res += s[x]; return res;
}

int main(){
	n = read();
	for (int i=1; i<=n; i++)
		x[i] = a[i] = read();
	sort(x+1, x+n+1); m = del();
	for (int i=1; i<=n; i++){
		a[i] = search(a[i]);
		update(s1, a[i], 1);
		update(s2, a[i], x[a[i]]);
	}
	pre = last = 0;
	for (int i=1; i<=n; i++)
		if (a[last] < a[i]){
			res = query(s2, a[i]) + 1LL*(n-query(s1, a[i]))*x[a[i]];
			printf("%lld\n", res-pre);
			last = i; pre = res;
		}
		else puts("0");
	return 0;
}

Submission Info

Judge Result