Submission #538906

#	Time	Username	Problem	Language	Result	Execution time	Memory
538906		amunduzbaev	Diversity (CEOI21_diversity)	C++17	64 / 100	78 ms	8616 KiB

diversity

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long
#define bug(x) cerr << #x << ' ' << x << '\n';

const int N = 3e5 + 5;
int a[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a, a + n);
	vector<int> tot;
	for(int i=0;i<n;){
		int j = i;
		while(j<n && a[j] == a[i]) j++;
		tot.push_back(j - i);
		i = j;
	}
	
	sort(tot.rbegin(), tot.rend());
	deque<int> tmp;
	for(int i=0;i<(int)tot.size();i++){
		if(i&1) tmp.push_back(tot[i]);
		else tmp.push_front(tot[i]);
	}
	
	//~ for(int i=0;i<(int)tmp.size();i++) cout<<tmp[i]<<" ";
	//~ cout<<endl;
	
	int pref = 0, res = n * (n + 1) * tot.size();
	for(int i=0;i<(int)tmp.size();i++){
		res -= pref * (pref + 1);
		res -= (n - pref - tmp[i]) * (n - pref - tmp[i] + 1);
		pref += tmp[i];
	}
	res >>= 1;
	cout<<res<<"\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