Submission #1229365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229365		raspy	Diversity (CEOI21_diversity)	C++20	64 / 100	79 ms	5100 KiB

diversity

#include <bits/stdc++.h>

#define vi vector<int>

#define int long long

using namespace std;

const int N = 3e5+5;

int ste[N];

signed main()
{
	int n, q;
	cin >> n >> q;
	vi a(n);
	for (int&v:a)
	{
		cin >> v;
		ste[v]++;
	}
	cin >> q >> q;
	sort(ste, ste+N);
	int rez=0;
	int levo = 0, desno = 0;
	for (int i = 0; i < N; i++)
	{
		if (ste[i] == 0)
			continue;
		rez += n*(n+1)/2;
		if (levo <= desno)
		{
			rez -= levo*(levo+1)/2;
			int ds = n-levo-ste[i];
			// cout << ste[i] << " " << levo << " " << ds << "\n";
			rez -= ds*(ds+1)/2;
			levo += ste[i];
		}
		else
		{
			rez -= desno*(desno+1)/2;
			int ds = n-desno-ste[i];
			// cout << ste[i] << " " << desno << " " << ds << " test\n";
			rez -= ds*(ds+1)/2;
			desno += ste[i];
		}
	}
	cout << rez << "\n";
	return 0;
}

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