Submission #713235

#	Time	Username	Problem	Language	Result	Execution time	Memory
713235		Pacybwoah	Diversity (CEOI21_diversity)	C++14	64 / 100	99 ms	13276 KiB

diversity

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

int main(){
    ll n,q;
    cin>>n>>q;
    if(q!=1) return 0;
    int a,b;
    vector<ll> vec(n);
    for(int i=0;i<n;i++) cin>>vec[i];
    cin>>a>>b;
    vector<ll> cnt(300001);
    for(int i=0;i<n;i++) cnt[vec[i]]++;
    vector<ll> p;
    for(int i=0;i<=300000;i++){
        if(cnt[i]>0) p.push_back(cnt[i]);
    }
    sort(p.begin(),p.end());
    vector<ll> f;
    for(int i=0;i<p.size();i+=2){
        f.push_back(p[i]);
    }
    for(int i=(p.size()%2==0?p.size()-1:p.size()-2);i>=0;i-=2) f.push_back(p[i]);
    ll sum=0,len=f.size();
    vector<ll> pre1(len),pre2(len);
    for(int i=1;i<len;i++){
        pre1[i]=pre1[i-1]+f[i]*i;
        pre2[i]=pre2[i-1]+f[i];
    }
    for(ll i=0;i<len;i++){
        sum+=f[i]*(f[i]+1)/2;
        sum+=f[i]*(pre1[len-1]-pre1[i]-(i-1)*(pre2[len-1]-pre2[i]));
    }
    cout<<sum<<"\n";
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<p.size();i+=2){
      |                 ~^~~~~~~~~

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