Submission #1097439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097439		alexander707070	Diversity (CEOI21_diversity)	C++14	64 / 100	44 ms	5468 KiB

diversity

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

int n,a[MAXN],q;

int br[MAXN],maxs,l,r,p[MAXN],len;
long long ans,mult,sum;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        br[a[i]]++;

        maxs=max(maxs,a[i]);
    }

    sort(br+1,br+maxs+1);
    for(int i=1;i<=maxs;i++){
        if(br[i]>0)r++;
    }
    r++;
    len=r-1;

    for(int i=1;i<=maxs;i++){
        if(br[i]==0)continue;

        if(i%2==0){
            l++; p[l]=br[i];
        }else{
            r--; p[r]=br[i];
        }
    }

    for(int i=1;i<=len;i++){
        ans+=(long long) (p[i])*(p[i]-1)/2+p[i];
    }

    for(int i=2;i<=len;i++){
        mult+=(long long) i*p[i];
        sum+=p[i];
    }

    for(int i=1;i<len;i++){
        ans+=p[i]*mult;

        mult-=sum+p[i+1];
        sum-=p[i+1];
    }

    cout<<ans<<"\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