Submission #1144312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144312		mnbvcxz123	Diversity (CEOI21_diversity)	C++20	64 / 100	363 ms	4680 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

#define int ll

constexpr int NAX=3e5+5;
constexpr int B=500;

set<int>ss;
int n,q,a[NAX];
int res[NAX],cnt[NAX],num[NAX];

void add(int x){
    num[cnt[x]]--;
    num[++cnt[x]]++;
    if(cnt[x]==B)ss.insert(x);
}
void del(int x){
    if(cnt[x]==B)ss.erase(x);
    num[cnt[x]--]--;
    num[cnt[x]]++;
}

int get(int N){
    vector<int>v;
    for(const int&x:ss)v.push_back(cnt[x]);
    sort(v.begin(),v.end());
    int l=0,r=0,tot=0,k=0,col=0;
    auto cal=[&](int x, int s, int d){
        tot+=(x*(x+1)*s+d*(2*x+1)*s*(s-1)/2+d*d*(s-1)*s*(2*s-1)/6)/2;
    };
    auto add=[&](int x, int s, int d){
        cal(x,s,d);
        cal(N-x-s*d,s,d);
    };
    for(int i=1;i<B;++i){
        col+=num[i];
        if(!num[i])continue;
        int x=(num[i]+1)/2;
        int y=num[i]/2;
        if(k)swap(x,y);
        add(l,x,i);
        add(r,y,i);
        l+=x*i;
        r+=y*i;
        k^=(num[i]&1);
    }
    col+=v.size();
    for(const int&x:v){
        if(k)add(r,1,x),r+=x;
        else add(l,1,x),l+=x;
        k^=1;
    }
    tot=col*N*(N+1ll)/2ll-tot;
    return tot;
}

mt19937 rng(time(nullptr));

int32_t main(){
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<array<int,3>>qq(q);
    for(int i=0;i<q;++i){
        cin>>qq[i][0]>>qq[i][1];
        qq[i][2]=i;
    }
    sort(qq.begin(),qq.end(),[&](const auto&x,const auto&y){
       if(x[0]/B!=y[0]/B)return x[0]<y[0];
       if(rng()&1)return x[1]>y[1];
       return x[1]<y[1];
    });
    int L=1,R=0;
    for(auto[l,r,id]:qq){
        while(R<r)add(a[++R]);
        while(L>l)add(a[--L]);
        while(R>r)del(a[R--]);
        while(L<l)del(a[L++]);
        res[id]=get(r-l+1);
    }
    for(int i=0;i<q;++i)
        cout<<res[i]<<'\n';
}

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