提出 #52981600

---

ソースコード 拡げる

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=400010;
int a[N],c[N],n,b[N],d[N];
ll cc[N];
void add(int x){
	for(;x<=n;x+=x&-x)++c[x];
}
void addc(int x,int v){
	for(;x<=n;x+=x&-x)cc[x]+=v;
}
ll sum(int x){
	int res=0;
	for(;x;x-=x&-x)res+=c[x];
	return res;
}
ll sumc(int x){
	ll res=0;
	for(;x;x-=x&-x)res+=cc[x];
	return res;
}
int main(){
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#endif
	#ifndef ONLINE_JUDGE
	freopen("1.txt","r",stdin);
	#endif
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i],b[i]=a[i];
	sort(a+1,a+1+n);
	int m=unique(a+1,a+1+n)-a,tot=0;
	ll totc=0,ans=0;
	for(int i=n;i;--i){
		int x=lower_bound(a+1,a+m,b[i])-a;
//		cout<<x<<'\n';
		ans+=(totc-sumc(x))-(tot-sum(x))*b[i];
//		cout<<sumc(x)<<'\n';
		++tot;
		totc+=b[i];
		add(x);
		addc(x,b[i]);
	}
	cout<<ans;
	return 0;
}

提出情報

ジャッジ結果