Submission #881899

#	Time	Username	Problem	Language	Result	Execution time	Memory
881899		TAhmed33	Diversity (CEOI21_diversity)	C++98	64 / 100	7047 ms	4128 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt")
typedef long long ll;
const int BUF_SZ = 1 << 15;
inline namespace Input {
char buf[BUF_SZ];
ll pos;
ll len;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (ll)fread(buf, 1, BUF_SZ, stdin);
		if (!len) { return EOF; }
	}
	return buf[pos++];
}
ll read_int() {
	ll x;
	char ch;
	ll sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') { sgn *= -1; }
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
	return x * sgn;
}
}  
inline namespace Output {
char buf[BUF_SZ];
ll pos;
void flush_out() {
	fwrite(buf, 1, pos, stdout);
	pos = 0;
}
void write_char(char c) {
	if (pos == BUF_SZ) { flush_out(); }
	buf[pos++] = c;
}
void write_int(ll x) {
	static char num_buf[100];
	if (x < 0) {
		write_char('-');
		x *= -1;
	}
	ll len = 0;
	for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
	write_char((char)('0' + x));
	while (len) { write_char(num_buf[--len]); }
	write_char('\n');
}
void init_output() { assert(atexit(flush_out) == 0); }
} 
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 () {
	init_output();
	n = read_int(), q = read_int();
	for (int i = 1; i <= n; i++) a[i] = read_int();
	while (q--) {
		memset(freq, 0, sizeof(freq));
		memset(freq2, 0, sizeof(freq2));
		int l = read_int(), r = read_int();
		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;
				}
			}
		}
		write_int(n1 * sq(o) - ans);
	}
}

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