Submission #944865

#	Time	Username	Problem	Language	Result	Execution time	Memory
944865		Halym2007	Diversity (CEOI21_diversity)	C++17	64 / 100	187 ms	20880 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#define sz size()
#define pb push_back
#define ll long long
#define ss second
const int N = 3e5 + 5;
int n, q, b[N], a[N];
ll jog;
deque <int> v, qq;
map <int, int> m;
ll p[N];
int main () {
//	freopen ("input1.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
	}
	for (int i = 1; i <= n; ++i) {
		m[b[i]]++;
	}
	for (auto i : m) {
		qq.pb (i.ss);
	}
	sort(qq.rbegin(), qq.rend());
	int tr = 0;
	for (int i : qq) {
		if (!tr) {
			v.pb (i);
		}
		else { 
			v.push_front(i);
		}
		tr ^= 1;
	}
	int git = (int)v.sz;
	ll sum1 = 0;
	p[git - 1] = v[git - 1];
	for (int i = git - 2; i >= 0; i--) {
		p[i] += p[i + 1] + v[i];
	}
	for (int i = git - 1; i >= 0; i--) {
		jog += (sum1 + p[i + 1]) * v[i];
		jog += (v[i] + 1LL) * v[i] / 2;
		sum1 += p[i];
	}	
	int l, r;
	cin >> l >> r;
	cout << jog;
}

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