Submission #1169536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169536		Troll321	Diversity (CEOI21_diversity)	C++20	64 / 100	241 ms	20160 KiB

diversity

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MAXN = 3e5 + 5;
const ll MAXQ = 5e4 + 5;
const ll MAX = 1e18;

ll n, q, k = 0, ans = MAX;
//								Compressed Cnt
ll cnt[MAXN], compressed[MAXN], ccnt[MAXN];
vector<ll> vec; 
set<ll> st;

ll count(ll iniIdx, ll sum[]) {
	ll out = 0, bef = 0;
	for (int i = iniIdx; i <= k; i+=2) {
		ll after = sum[(iniIdx+1)%2] + (sum[iniIdx%2]-bef-ccnt[i]);
		out += bef*bef + after*after;
		bef += ccnt[i];
	}

	return out;
}

ll calc() {
	ll out = n*k*(n+1) - n*(k-1);
	ll sqSum = 0;

	sort(ccnt+1, ccnt+k+1);

	ll sum[2] = {0,0};

	for (int i = 1; i <= k; ++i) {
		sum[i%2] += ccnt[i];
	}

	sqSum += count(1, sum);
	sqSum += count(2, sum);

	out = (out - sqSum) / 2;
	return out;
}

void compress() {
	for (auto it = st.begin(); it != st.end(); it++) {
		k++;
		compressed[(*it)] = k;
		ccnt[k] = cnt[(*it)];
	}
}

int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		ll tmp; cin >> tmp;
		st.insert(tmp);
		cnt[tmp]++;
	}

	compress();

	ll _tmp;
	cin >> _tmp >> _tmp;

	for (int i = 1; i <= k; ++i) {
		vec.push_back(i);
	}

	sort(vec.begin(), vec.end());

	ans = calc();

	cout << ans << "\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