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;
long long n,q;
long long nr, ans;
long long a[300005];
long long fr[300005];
bool comp(int a, int b)
{
return fr[a] > fr[b];
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
fr[ a[i] ] ++;
}
int l, r;
cin>>l>>r;
vector<pair<int, int>> v, aux;
for(int i=1;i<=n;i++)
if(fr[ a[i] ])
{
v.push_back({fr[ a[i] ], a[i] });
fr[ a[i] ] = 0;
}
/*
for(auto it : v)
cout<<it.first<<' '<<it.second<<'\n';
return 0;
*/
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
int sum = 0;
while((int)v.size() > 2)
{
if(sum + v.back().first <= n/2)
{
sum += v.back().first;
aux.push_back(v.back());
v.pop_back();
}
else
break;
}
reverse(v.begin(), v.end());
while(!v.empty())
{
aux.push_back(v.back());
v.pop_back();
}
/*
for(auto it : aux)
cout<<it.first<<' '<<it.second<<'\n';
return 0;
*/
n=0;
for(auto it : aux)
{
for(int j=1; j<= it.first; j++)
{
n++;
a[n] = it.second;
}
}
ans=0;
for(int i=1;i<=n;i++)
{
nr = 1;
for(int j=i;j<=n;j++)
{
if(j>i && a[j] != a[j-1])
nr++;
ans += nr;
}
}
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... |