#include <bits/stdc++.h>
using namespace std;
int FT[3000002];
void updateFT(int i,int val){
while(i<300000){
FT[i]+=val;
i+=i&-i;
}
}
int getFT(int i){
int s=0;
while(i>0){
s+=FT[i];
i-=i&-i;
}
return s;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<long long>a(n+1,0),val,pre(n+1,0),suf(n+1,0);
for(int i=1;i<=n;i++)cin>>a[i],val.push_back(a[i]);
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
for(int i=1;i<=n;i++)a[i]=int(lower_bound(val.begin(),val.end(),a[i])-val.begin())+1;
for(int i=1;i<=n;i++)pre[i]=getFT(a[i]-1),updateFT(a[i],1);
memset(FT,0,sizeof(FT));
for(int i=n;i>=1;i--)suf[i]=getFT(a[i]-1),updateFT(a[i],1);
long long ans=0;
for(int i=1;i<=n;i++)ans+=pre[i]*suf[i];
cout<<ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |