Submission #572493

#	Time	Username	Problem	Language	Result	Execution time	Memory
572493		valerikk	Diversity (CEOI21_diversity)	C++17	100 / 100	2390 ms	6012 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;
const int Q = 5e4 + 11;
const int B = 450;

long long solve(vector<pair<int, int>> c) {
	sort(c.rbegin(), c.rend());

	int n = 0, k = 0;
	
	deque<pair<int, int>> q;

	int t = 0;
	for (const auto &[x, y] : c) {
		n += x * y;
		k += y;
		if (t) {
			q.push_back({x, (y + 1) / 2});	
			if (y > 1)
				q.push_front({x, y / 2});
		} else {
			q.push_front({x, (y + 1) / 2});
			if (y > 1)
				q.push_back({x, y / 2});
		}

		t = (t + y) & 1;
	}

	vector<pair<int, int>> z(q.begin(), q.end());

	long long all = n * 1ll * (n + 1) / 2 * k;

	long long bad = 0;

	long long sum = 0;
	for (int i = 0; i < (int) z.size(); ++i) {
		const auto &[x, y] = z[i];

		bad += sum * sum * y;
		bad += sum * x * y * (y - 1);
		bad += sum * y;
		bad += x * 1ll * y * (y - 1) / 2;
		bad += (y - 1) * 1ll * y * (2 * (y - 1) + 1) / 6 * x * x;

		sum += x * y;
	}

	sum = 0;
	for (int i = (int) z.size() - 1; i >= 0; --i) {
		const auto &[x, y] = z[i];

		bad += sum * sum * y;
		bad += sum * x * y * (y - 1);
		bad += sum * y;
		bad += x * 1ll * y * (y - 1) / 2;
		bad += (y - 1) * 1ll * y * (2 * (y - 1) + 1) / 6 * x * x;

		sum += x * y;
	}

	bad /= 2;

	// cout << all << " " << bad << "\n";

	long long res = all - bad;

	return res;
}

int n, q;
int a[N];
int l[Q], r[Q];
int ord[Q];

struct Cnt {
	int cnt[N];
	int scnt[N];
	bool used[N];
	vector<int> s;

	void add(int x) {
		--scnt[cnt[x]];
		++cnt[x];
		if (++scnt[cnt[x]] == 1 && !used[cnt[x]] && cnt[x] > 0) {
			s.push_back(cnt[x]);
			used[cnt[x]] = true;
		}
	}

	void remove(int x) {
		--scnt[cnt[x]];
		--cnt[x];
		if (++scnt[cnt[x]] == 1 && !used[cnt[x]] && cnt[x] > 0) {
			s.push_back(cnt[x]);
			used[cnt[x]] = true;
		}
	}

	vector<pair<int, int>> get_cnts() {
		vector<pair<int, int>> res;
		vector<int> s1;
		for (int i : s) {
			if (scnt[i] > 0) {
				res.push_back({i, scnt[i]});
				s1.push_back(i);
			} else {
				used[i] = false;
			}
		}
		s = s1;
		return res;
	}

	Cnt() {
		for (int i = 0; i < N; ++i) {
			++scnt[cnt[i]];
		}
		s.reserve(N);
	}
} cnt;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	for (int i = 0; i < q; ++i) {
		cin >> l[i] >> r[i];
		--l[i];
	}

	iota(ord, ord + q, 0);
	sort(ord, ord + q, [&] (const int &i, const int &j) {
		int blocki = l[i] / B;
		int blockj = l[j] / B;
		return make_pair(blocki, (blocki & 1) ? -r[i] : r[i]) < make_pair(blockj, (blockj & 1) ? -r[j] : r[j]);
	});

	vector<long long> ans(q);

	int cl = 0, cr = 0;
	for (int i = 0; i < q; ++i) {
		while (cl > l[ord[i]]) {
			cnt.add(a[--cl]);
		}
		while (cr < r[ord[i]]) {
			cnt.add(a[cr++]);
		}
		while (cl < l[ord[i]]) {
			cnt.remove(a[cl++]);
		}
		while (cr > r[ord[i]]) {
			cnt.remove(a[--cr]);
		}

		ans[ord[i]] = solve(cnt.get_cnts());
	}

	for (int i = 0; i < q; ++i) {
		cout << ans[i] << "\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: 36 / 36