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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,q;
int a[300005];
int fr[300005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
int mxm=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
fr[a[i]]++;
mxm=max(mxm,a[i]);
}
int qle,qri;
for(int i=1;i<=q;i++)
{
cin>>qle>>qri;
}
sort(fr+1,fr+1+mxm);
vector<int> vle,vri;
for(int i=1;i+1<=mxm;i+=2)
{
if(i%2==1)
{
vle.push_back(fr[i]);
vri.push_back(fr[i+1]);
}
else
{
vle.push_back(fr[i+1]);
vri.push_back(fr[i]);
}
}
if(mxm%2==1) vle.push_back(fr[mxm]);
vector<int> aux = vle;
for(int i=(int)vri.size()-1;i>=0;i--)
aux.push_back(vri[i]);
long long pref=0,rez=0;
for(auto x:aux)
{
rez += (pref+x)*(n-pref);
rez -= x*(x-1)/2;
pref += x;
}
cout<<rez;
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... |