Submission #783821

#	Time	Username	Problem	Language	Result	Execution time	Memory
783821		Deepesson	Diversity (CEOI21_diversity)	C++17	100 / 100	5139 ms	25004 KiB

diversity

#include <bits/stdc++.h>
#define MAX 305000
#define SQRT 800
using ll = long long;
ll array[MAX],freq[MAX];
ll N,Q;
typedef std::pair<ll,ll> pii;
typedef std::pair<pii,ll> ppi;
ll l[MAX],r[MAX],resp[MAX];
std::vector<ppi> queries;
ll sizes[MAX];
std::vector<ll> casos;
ll foier[MAX];
bool pesado[MAX];
void add(ll x){
	ll elemento = array[x];
	if(!pesado[elemento])
	sizes[freq[elemento]]--;
	++freq[elemento];
	if(!pesado[elemento])
	sizes[freq[elemento]]++;
}
void remove(ll x){
	ll elemento = array[x];
	if(!pesado[elemento])
	sizes[freq[elemento]]--;
	--freq[elemento];
	if(!pesado[elemento])
	sizes[freq[elemento]]++;
}
ll rodanda=42;
ll precomp[MAX];
typedef std::pair<ll,ll> pll;
ll gaussian(ll first,ll last,ll size){
	return (first+last)*size/2LL;
}
std::vector<ll> separado;
ll getans(ll length){
	++rodanda;
	std::vector<pii> sz;
	ll base=0;
	for(ll i=1;i!=SQRT;++i){
		base+=((i*(i+1))/2)*sizes[i];
		if(sizes[i]){
			sz.push_back({i,sizes[i]});
		}
	}
	std::vector<pii> secondary;
	for(auto&x:separado){
		if(freq[x]){
			base+=((freq[x]*(freq[x]+1))/2);
			secondary.push_back({freq[x],1});
		}
	}
	std::random_shuffle(secondary.begin(),secondary.end());
	std::sort(secondary.begin(),secondary.end());
	int c1=sz.size()-1,c2=secondary.size()-1;
	std::deque<pll> ans;
	ll count=0;
	for(ll i = 0;i!=sz.size()+secondary.size();++i){
		ll agora = count&1;
		pii analise;
		pii a1={-1,-1},a2={-1,-1};
		if(c1>=0){
			a1=sz[c1];
		}
		if(c2>=0){
			a2=secondary[c2];
		}
		if(a1>a2){
			analise=a1;
			--c1;
		}else {
			analise=a2;
			--c2;
		}
		ll metade_maior = analise.second/2 + (analise.second%2);
		ll metade_menor = analise.second/2;
		if(agora){
			ans.push_back({analise.first,metade_maior});
			ans.push_front({analise.first,metade_menor});
		}else {
			ans.push_front({analise.first,metade_maior});
			ans.push_back({analise.first,metade_menor});
		}
		count+=analise.second;
	}
	ll res=0,somado=0;
	ll foi=0;
	for(ll i=0;i!=ans.size();++i){
		ll tam = ans[i].first;
		ll sum_somado=gaussian(somado,somado+(ans[i].second-1)*ans[i].first,ans[i].second);
		ll sum_foi = gaussian(foi,foi+(ans[i].second-1),ans[i].second);
		res+=ans[i].first*sum_somado;
		res+=sum_foi*ans[i].first*ans[i].first;
		res-=length*ans[i].first*sum_foi;
		ll s=0;
		ll tenta_prever=0,brute=0;
		if(ans[i].second)
		{
			ll iteracoes = gaussian(0,ans[i].second-1,ans[i].second);
			ll tamk = iteracoes*tam;
			tenta_prever=ans[i].second*somado*foi;
			tenta_prever+=somado*iteracoes;
			tenta_prever+=iteracoes*tam*foi;
			tenta_prever+=tam*precomp[ans[i].second-1];
		}
		tenta_prever*=2*tam;
		res+=tenta_prever;
		foi+=ans[i].second;
		somado+=tam*ans[i].second;
	}
	return base+res;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	for(ll i=1;i!=MAX;++i){
		precomp[i]=precomp[i-1]+i*i;
	}
	std::map<int,int> aparece;
	std::cin>>N>>Q;
	for(ll i=0;i!=N;++i){
		std::cin>>array[i];
		aparece[array[i]]++;
	}
	std::vector<pii> mais_frequentes;
	for(auto&x:aparece)mais_frequentes.push_back({x.second,x.first});
	std::sort(mais_frequentes.begin(),mais_frequentes.end());
	std::reverse(mais_frequentes.begin(),mais_frequentes.end());
	for(int i=0;i<std::min((ll)mais_frequentes.size(),(ll)SQRT);++i){
		separado.push_back(mais_frequentes[i].second);
		pesado[mais_frequentes[i].second]=1;
	}
	for(ll i=0;i!=Q;++i){
		std::cin>>l[i]>>r[i];
		--l[i];--r[i];
		queries.push_back({{l[i]/600,r[i]},i});
	}
	std::sort(queries.begin(),queries.end());
	ll curl=0,curr=-1;
	for(auto&x:queries){
		ll querl = l[x.second],querr=r[x.second];
		ll ans=0;
		while(curr<querr){///Vai para a direita removendo elementos
			++curr;
			add(curr);
		}
		while(curl>querl){///Diminui o cursor aumentando elementos
			--curl;
			add(curl);
		}
		while(curl<querl){///Vai para a direita removendo elementos
			remove(curl);
			++curl;
		}
		while(curr>querr){///Diminui o cursor diminuindo elementos
			remove(curr);
			--curr;
		}	
		ans=getans(querr-querl+1);
		resp[x.second]=ans;
	}
	for(ll i=0;i!=Q;++i){
		std::cout<<resp[i]<<"\n";
	}
}

Compilation message (stderr)

diversity.cpp: In function 'll getans(ll)':
diversity.cpp:60:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(ll i = 0;i!=sz.size()+secondary.size();++i){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diversity.cpp:90:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(ll i=0;i!=ans.size();++i){
      |             ~^~~~~~~~~~~~
diversity.cpp:102:7: warning: unused variable 'tamk' [-Wunused-variable]
  102 |    ll tamk = iteracoes*tam;
      |       ^~~~
diversity.cpp:97:6: warning: unused variable 's' [-Wunused-variable]
   97 |   ll s=0;
      |      ^
diversity.cpp:98:21: warning: unused variable 'brute' [-Wunused-variable]
   98 |   ll tenta_prever=0,brute=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