Submission #784016

#	Time	Username	Problem	Language	Result	Execution time	Memory
784016		HamletPetrosyan	Diversity (CEOI21_diversity)	C++17	64 / 100	42 ms	11244 KiB

diversity

/// -- -- ---- --- -- --
/// no. c.ompi le  ti:me
/// -- -- ---- --- -- --

#include <bits/stdc++.h>
using namespace std;
void abandoned_precalc();

#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((int)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 3e5 + 5;

ll n, q;
ll a[N];
ll cnt[N];

void solve(){
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		cnt[a[i]]++;
	}
	for(int i = 0, x, y; i < q; i++){
		cin >> x >> y;
	}
	vector<ll> v, w;
	ll sum = 0;
	for(int i = 1; i <= 300000; i++){
		if(cnt[i]) v.add(cnt[i]), sum += cnt[i];
	}
	sort(all(v));
	for(int i = 0; i < len(v); i++){
		if(i < len(v) / 2) w.add(v[2 * i + 1]);
		else w.add(v[(len(v) - 1 - i) * 2]);
	}
//	for(auto x : w){
//		cout << x << " ";
//	}
//	cout << endl;
	ll ans = 0, pref = 0;
	for(int i = 0; i < len(w); i++){
		ans += (pref + w[i]) * (sum - pref);
		ans -= w[i] * (w[i] - 1) / 2;
		pref += w[i];
	}

	cout << ans << endl;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(9);

	abandoned_precalc();
	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// just a reminder. ubuntu password is i o i
/// ---- - --------  ------ -------- -- - - -














void abandoned_precalc(){
	
}

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