Submission #478638

#	Time	Username	Problem	Language	Result	Execution time	Memory
478638		CSQ31	Diversity (CEOI21_diversity)	C++17	64 / 100	114 ms	7968 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+1;
int cnt[MAXN+1];
typedef long long int ll;
int main()
{
	int n,q;
	cin>>n>>q;
	vector<int>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	if(q==1){
		int l,r;
		cin>>l>>r;
		vector<int>c;
		for(int x:a)cnt[x]++;
		for(int i=1;i<=MAXN;i++){
			if(cnt[i])c.push_back(cnt[i]);
		}
		sort(c.begin(),c.end());
		deque<int>lef,rig;
		ll lsum = 0,rsum =0;
		for(int x:c){
			if(lsum <= rsum){
				lsum+=x;
				lef.push_back(x);
			}else{
				rsum+=x;
				rig.push_front(x);
			}
		}
		vector<int>fin;
		while(!lef.empty()){
			fin.push_back(lef.front());
			lef.pop_front();
		}
		while(!rig.empty()){
			fin.push_back(rig.front());
			rig.pop_front();
		}
		int i = 0;
		ll ans = 0;
		for(int x:fin){
			//cout<<x<<" ";
			ans+=(i+x) * 1LL * (n-i) - (x*1LL*(x-1))/2;
			i+=x;
		}
		cout<<ans<<'\n';
		
	}
	
	
}

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36