Submission #576857

#	Time	Username	Problem	Language	Result	Execution time	Memory
576857		amunduzbaev	Diversity (CEOI21_diversity)	C++17	18 / 100	65 ms	2684 KiB

diversity

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int int64_t

const int N = 3e5 + 5;
const int Q = 5e4 + 5;
const int B = 550;
int a[N], l[Q], r[Q];
int cnt[N], res[Q];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	vector<int> p;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<q;i++){
		cin>>l[i]>>r[i];
		l[i]--;
		p.push_back(i);
	}
	sort(p.begin(), p.end(), [&](int i, int j){
		if(l[i] / B != l[j] / B){
			return l[i] < l[j];
		} 
		return r[i] < r[j];
	});
	map<int, int> mm;
	auto add = [&](int i){
		if(cnt[a[i]]){
			mm[cnt[a[i]]]--;
			if(!mm[cnt[a[i]]]) mm.erase(cnt[a[i]]);
		} 
		cnt[a[i]]++;
		mm[cnt[a[i]]]++;
	};
	auto del = [&](int i){
		assert(cnt[a[i]]);
		mm[cnt[a[i]]]--;
		if(!mm[cnt[a[i]]]) mm.erase(cnt[a[i]]);
		cnt[a[i]]--;
		if(cnt[a[i]]) mm[cnt[a[i]]]++;
	};
	
	int lx = 0, rx = 0;
	for(auto i : p){
		while(rx > r[i]){ 
			del(--rx);
		}
		while(rx < r[i]){
			add(rx++);
		}
		while(lx > l[i]){
			add(--lx);
		}
		while(lx < l[i]){
			del(lx++);
		}
		
		int ls = 0, rs = 0;
		deque<ar<int, 2>> L, R;
		for(auto [v, c] : mm){
			int b = (c + 1) / 2, s = c - b;
			if(ls > rs) swap(b, s);
			if(b) L.push_back({v, b}), ls += b;
			if(s) R.push_front({v, s}), rs += s;
		}
		
		L.insert(L.end(), R.begin(), R.end());
		//~ for(auto x : L) cout<<x[0]<<" "<<x[1]<<"\n";
		int sum = 0, sumj = 0, p = 0;
		for(auto [v, c] : L){
			res[i] += v * (p * c + c * (c - 1) / 2) * sum;
			res[i] -= v * sumj;
			res[i] += (c * c * (c + 1) / 2 - c * (c + 1) * (2 * c + 1) / 6) * v * v;
			sumj += v * (p * c + c * (c - 1) / 2);
			p += c, sum += v * c;
		}
		res[i] += sum * (sum + 1) / 2;
		//~ cout<<"\n";
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

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