Submission #881898

#	Time	Username	Problem	Language	Result	Execution time	Memory
881898		TAhmed33	Diversity (CEOI21_diversity)	C++98	64 / 100	7044 ms	5908 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt")
typedef long long ll;
const int MAXN = 3e5 + 25;
const int ORIGIN = 300000;
int n, a[MAXN], q, n1;
int freq[MAXN], freq2[MAXN];
inline ll sq (ll x) {
	return ((x * (x + 1)) >> 1ll);
}
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while (q--) {
		memset(freq, 0, sizeof(freq));
		memset(freq2, 0, sizeof(freq2));
		int l, r;
		cin >> l >> r;
		ll o = r - l + 1;
		n1 = 0;
		for (int i = l; i <= r; i++) {
			if (freq[a[i]]) freq2[freq[a[i]]]--;
			else n1++;
			freq2[++freq[a[i]]]++;
		}
		int c = 0;
		ll ans = 0;
		ll p = 0, q = 0;
		for (int i = 1; i <= ORIGIN; i++) {
			ll j = freq2[i];
			for (int l = 1; l <= j; l++) {
				c ^= 1;
				if (c) {
					ans += sq(p) + sq(o - p - i); p += i;
				} else {
					ans += sq(q) + sq(o - q - i); q += i;
				}
			}
		}
		cout << n1 * sq(o) - ans << '\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