Submission #1357970

---

Source Code Expand

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <map>
#define int long long
using namespace std;

typedef pair<int,int> P;

int n,bit[100001];

void add(int i,int x){
	while(i <= n + 1){
		bit[i] += x;
		i += i & -i;
	}
}

int sum(int i){
	int s = 0;
	while(i){
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

signed main(){
	int a[100000],ans[100000] = {},prev = 0;
	map<int,int> mp;
	vector<P> vec;
	cin >> n;
	for(int i = 0;i < n;i++) {
		cin >> a[i];
		vec.push_back(P(a[i],i));
	}
	sort(vec.begin(),vec.end(),greater<P>());
	for(int i = n - 1;i >= 0;i--) mp[a[i]] = i;
	for(auto it = mp.begin();it != mp.end();it++){
		ans[it->second] = it->first - prev;
		prev = it->first;
	}
	for(int i = 0;i < n;i++){
		add(vec[i].second + 1,1);
		ans[vec[i].second] *= sum(n) - sum(vec[i].second);
	}
	for(int i = 0;i < n;i++) cout << ans[i] << endl;
}

Submission Info

Judge Result