Submission #826978

#TimeUsernameProblemLanguageResultExecution timeMemory
826978aminDiversity (CEOI21_diversity)C++14
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int fre[300001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,q; cin>>n>>q; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; fre[a[i]]++; } vector<pair<int,int> >v; for(int i=0;i<n;i++) { if(fre[a[i]]==0) { continue; } v.push_back({fre[a[i]],a[i]}); fre[a[i]]=0; } sort(v.begin(),v.end()); reverse(v.begin(),v.end()); vector<pair<int,int > >s2; vector<pair<int,int > >s1; ll sz1=0,sz2=0; ll k=v.size(); ll ans=n*(n+1)/2*k; for(auto i:v) { // cout<<i.first<<' '<<i.second<<endl; if(sz1<=sz2) { ans-=sz1*(sz1+1)/2; ll j=n-sz1-i.first; ans-=j*(j+1)/2; s1.push_back(i); sz1+=i.first; }else { ans+=sz2*(sz2+1)/2; ll j=n-sz2-i.first; ans-=j*(j+1)/2; s2.push_back(i); sz2+=i.first; } } reverse(s2.begin(),s2.end()); vector<int>b; for(auto i:s1) { while(i.first--) { b.push_back(i.second); } } for(auto i:s2) { while(i.first--) { b.push_back(i.second); } } while(q--) { int l,r; cin>>l>>r; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...