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;
#include <bits/extc++.h>
using namespace __gnu_pbds;
typedef tree<pair<long long,long long> , null_type, less<pair<long long,long long> >, rb_tree_tag, tree_order_statistics_node_update> ost;
const long long MOD=1e9+7;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ost tree,tree2;
long long n;
cin>>n;
long long niza[n];
for(long long i=0; i<n; i++)
{
cin>>niza[i];
}
long long l[n],r[n];
map<long long,long long> mapa,mapa2;
for(long long i=0; i<n; i++)
{
mapa[niza[i]]++;
tree.insert({niza[i],mapa[niza[i]]});
long long tmp=tree.order_of_key({niza[i],1});
l[i]=tmp;
}
for(long long i=n-1; i>=0; i--)
{
mapa2[niza[i]]++;
tree2.insert({niza[i],mapa2[niza[i]]});
long long tmp=tree2.order_of_key({niza[i],1});
r[i]=tmp;
}
long long res=0;
for(long long i=0; i<n; i++)
{
res+=l[i]*r[i];
}
cout<<res<<endl;
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... |