This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair <ll,ll> pl;
typedef vector<pl> vpl;
#define s second
#define f first
int n;
vl ft1,ft2;
int lsb(int x){
return x & (-x);
}
ll query(int ind, bool who){
ll res=0;
while(ind){
if(who) res+=ft1[ind];
else res+=ft2[ind];
ind-=lsb(ind);
}
return res;
}
void update(int ind, ll value, bool who){
while(ind<=n){
if(who) ft1[ind]+=value;
else ft2[ind]+=value;
ind+=lsb(value);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
ft1.assign(n+1,0); ft2.assign(n+1,0);
ll a[n];
vpl aux(n);
for(int i=0; i<n; i++){
int x; cin>>x; aux[i]={x,i};
}
sort(aux.begin(),aux.end()); a[aux[0].s]=1; int temp=1;
for(int i=1; i<n; i++){
if(aux[i].f==aux[i-1].f) a[aux[i].s]=temp;
else temp++, a[aux[i].s]=temp;
}
//for(auto &x: a) cout<<x<<" "; cout<<endl;
ll mx=0;
for(int i=n-1; i>=0; i--){
mx=max(mx,a[i]);
update(a[i],1,1);
}
//cout<<query(mx-1,1)<<endl;
//int top=n+99;
ll ans=0;
for(int i=0; i<n; i++){
update(a[i],-1,1);
//cout<<query(a[i]-1,0)<<" "<<query(a[i]-1,1)<<endl;
ans+=query(a[i]-1,0)*(query(a[i]-1,1));
update(a[i],1,0);
}
cout<<ans<<endl;
}
# | 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... |