Submission #1606566

---

Source Code Expand

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

typedef pair<int,int> P;

signed main(){
	int n,x[100000],ans[100000] = {},su = 0,ansu = 0;
	vector<P> vec;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> x[i];
		su += x[i];
		vec.push_back(P(x[i],-i));
	}
	sort(vec.begin(),vec.end(),greater<P>());
	int lind = n,lup = 0,last = vec[0].first,sum = 0;
	for(int i = 0;i < n;i++){
		sum += (last - vec[i].first) * i;
		last = vec[i].first;
		if(!vec[i].second){
			ans[lup] = sum;
			ans[0] = su - ansu - sum;
			break;
		}
		if(lind > -vec[i].second){
			if(i) ans[lup] = sum;
			lup = -vec[i].second;
			ansu += sum;
			sum = 0;
		}
		lind = -vec[i].second;
	}
	for(int i = 0;i < n;i++) cout << ans[i] << endl;
}

Submission Info

Judge Result