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>
#define int long long
using namespace std;
const int N=3e5+5;
vector<int> v(N);
vector<int> f[N];
struct fenwick{
int d[N];
void update(int idx,int vl){
while(idx<N){
d[idx]+=vl;
idx+=idx&(-idx);
}
}
int query(int idx){
int sm=0;
while(idx>0){
sm+=d[idx];
idx-=(idx&-idx);
}
return sm;
}
} fe;
int32_t main(){
cin.tie(NULL)->sync_with_stdio(false);
int ans=0;
int n; cin >> n;
vector<int> a;
for(int i=1 ; i<=n ; i++){
fe.update(i,1);
}
for(int i=1 ; i<=n ; i++) cin >> v[i],a.push_back(v[i]);
sort(a.begin(),a.end());
for(int i=1 ; i<=n ; i++){
v[i]=lower_bound(a.begin(),a.end(),v[i])-a.begin()+1;
}
for(int i=1 ; i<=n ; i++){
f[v[i]].push_back(i);
}
for(int i=n ; i>=1 ; i--){
if(f[i].empty()) continue;
for(int j:f[i]){
fe.update(j,-1);
}
for(int j:f[i]){
ans+=fe.query(j)*(fe.query(n)-fe.query(j));
}
}
cout << ans << '\n';
}
# | 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... |