Submission #1169797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169797		Troll321	Diversity (CEOI21_diversity)	C++20	64 / 100	7090 ms	13168 KiB

diversity

#include <bits/stdc++.h>
#define fi first
#define se second
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma,popcnt,bmi2,bmi,lzcnt")
#pragma unroll 2
#include <immintrin.h>
uint32_t odd_bits(uint32_t x){return _pext_u32(x, 0x55555555u);}

#define gc getchar

namespace fastio{
	template <typename T> inline void sca(T &angka){
		T kali = 1; angka = 0; char input = gc();
		while (input < '0' || input > '9'){if (input == '-') kali = -1; input = gc();}
		while(input >= '0' && input <= '9')angka = (angka << 3) + (angka << 1) + input - 48, input = gc();
		angka *= kali;
	}
	template <typename T> inline void scans(T &s){
		s = ""; char input = gc(); while(input != ' ' && input != '\n') s += input, input = gc();
	}
	template <typename T> inline void scanln(T &s){
		s = ""; char input = gc(); while(input != '\n') s += input, input = gc();
	}
	template <typename FIRST, typename... REST > inline void scan( FIRST& first, REST&... rest ); // utama
	inline void scan() {}
  	template <typename FIRST, typename... REST > inline void scan( FIRST& first, REST&... rest ){sca(first);scan(rest...);}
}using namespace fastio;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MAXN = 3e5 + 5;
const ll MAXQ = 5e4 + 5;
const ll MAX = 1e18;
const ll BLOCK = 550;
const ll MAXBLOCK = MAXN/BLOCK+5;

ll n, q;
ll answer[MAXQ];
ll arr[MAXN];
vector<pair<ll, pll>> blocks[MAXBLOCK];

ll freq[MAXN];
map<ll,ll> comps[MAXBLOCK];
map<ll,ll>* comp;

ll calc(ll l, ll r) {
	ll n = r-l+1;
	ll k = 0;
	ll sqSum = 0;

	ll bef[2] = {0,0};
	ll nowpar = 1;
	for(auto i : (*comp)) {
		k += i.se;

		// i.fi (length)
		// i.se (banyak)

		for (ll parity = 0; parity <= 1; ++parity) {
			ll len = 0;

			if(nowpar != parity) {
				len = i.se >> 1;
			} else {
				len = (i.se+1) >> 1;
			}

			sqSum += len*bef[parity]*bef[parity] + (len-1)*len*bef[parity]*i.fi + (len-1)*len*(2*len-1)/6*i.fi*i.fi;
			sqSum += len*(n*n + bef[parity]*bef[parity]) - 2*len*n*bef[parity] + len*(len+1)*i.fi*(bef[parity]-n) + len*(len+1)*(2*len+1)/6*i.fi*i.fi;

			bef[parity] += i.fi * len;
		}

		nowpar = ((ll)nowpar+i.se) % 2;
	}

	ll out = n*k*(n+1) - n*(k-1);
	out = (out - sqSum) >> 1;
	return out;
}

bool cmp(pair<ll,pll> a, pair<ll,pll> b) {
	// if(a.se.se == b.se.se) {return a.se.fi < b.se.fi;}
	return a.se.se < b.se.se;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	scan(n, q);
	for (int i = 1; i <= n; ++i) {
		scan(arr[i]);
	}

	for (int i = 1; i <= q; ++i) {
		pll input;
		scan(input.fi, input.se);
		blocks[input.fi/BLOCK].push_back({i, input});
	}

	for (int nowBlock = 0; nowBlock <= n/BLOCK; ++nowBlock) {
		if(blocks[nowBlock].empty()) {continue ;}
		sort(blocks[nowBlock].begin(), blocks[nowBlock].end(), cmp);

		// Reset freq, comp
		memset(freq, 0, sizeof(freq));
		comp = &comps[nowBlock];

		ll pl = 1 + nowBlock*BLOCK, pr = pl;
		freq[arr[pl]]++;
		(*comp)[freq[arr[pl]]]++;
		for (int i = 0; i < blocks[nowBlock].size(); ++i) {
			ll ansIdx = blocks[nowBlock][i].fi;
			pll range = blocks[nowBlock][i].se;

			// Shift pl
			while (pl < range.fi) {
				if(--(*comp)[freq[arr[pl]]] == 0) {(*comp).erase(freq[arr[pl]]);}
				if(--freq[arr[pl]] > 0) {(*comp)[freq[arr[pl]]]++;}
				pl++;
			}
			while (pl > range.fi) {
				pl--;
				freq[arr[pl]]++;
				(*comp)[freq[arr[pl]]]++;
				if(freq[arr[pl]] > 1) {
					if(--(*comp)[freq[arr[pl]]-1] == 0){
						(*comp).erase(freq[arr[pl]]-1);
					}
				}
			}

			// Shift pr
			while(pr < range.se) {
				pr++;
				freq[arr[pr]]++;
				(*comp)[freq[arr[pr]]]++;
				if(freq[arr[pr]] > 1) {
					if(--(*comp)[freq[arr[pr]]-1] == 0){
						(*comp).erase(freq[arr[pr]]-1);
					}
				}
			}

			answer[ansIdx] = calc(range.fi, range.se);
		}
	}

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