Submission #1084179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084179		onlk97	Diversity (CEOI21_diversity)	C++14	100 / 100	1486 ms	6228 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
int L,R;
int a[300010];
long long freq[300010],freq2[300010];
bitset <300010> have;
long long calcans(){
    long long ans=0,lps=0,rps=0,s=R-L+1;
    for (int i=have._Find_first(); i<300010; i=have._Find_next(i)){
        long long cntl,cntr;
        int f;
        if (lps<=rps){
            f=min(freq2[i],(rps-lps)/i+1);
            cntl=f+(freq2[i]-f)/2,cntr=(freq2[i]-f+1)/2;
        } else {
            f=min(freq2[i],(lps-rps)/i+1);
            cntl=(freq2[i]-f+1)/2,cntr=f+(freq2[i]-f)/2;
        }
        ans+=cntl*lps*lps+cntl*(cntl+1)*lps*i+cntl*(cntl+1)/2*(2*cntl+1)/3*i*i;
        ans-=s*(lps+i+lps+i*cntl)*cntl/2;
        lps+=cntl*i;
        long long t=s-rps;
        ans+=cntr*t*t-cntr*(cntr-1)*t*i+(cntr)*(cntr-1)/2*(2*cntr-1)/3*i*i;
        ans-=s*(t+t-(cntr-1)*i)*cntr/2;
        rps+=cntr*i;
    }
    return s*(s+1)/2-ans;
}
const int BLOCK=800;
bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
    int ax=a.first.first/BLOCK,bx=b.first.first/BLOCK;
    if (ax!=bx) return ax<bx;
    return a.first.second<b.first.second;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>a[i];
    pair <pair <int,int>,int> qu[q+1];
    for (int i=1; i<=q; i++){
        cin>>qu[i].first.first>>qu[i].first.second;
        qu[i].second=i;
    }
    sort(qu+1,qu+q+1,cmp);
    L=1; R=0;
    long long op[q+1];
    for (int i=1; i<=q; i++){
        while (R<qu[i].first.second){
            R++;
            if (freq[a[R]]){
                freq2[freq[a[R]]]--;
                if (!freq2[freq[a[R]]]) have[freq[a[R]]]=0;
            }
            freq[a[R]]++;
            if (!freq2[freq[a[R]]]) have[freq[a[R]]]=1;
            freq2[freq[a[R]]]++;
        }
        while (L>qu[i].first.first){
            L--;
            if (freq[a[L]]){
                freq2[freq[a[L]]]--;
                if (!freq2[freq[a[L]]]) have[freq[a[L]]]=0;
            }
            freq[a[L]]++;
            if (!freq2[freq[a[L]]]) have[freq[a[L]]]=1;
            freq2[freq[a[L]]]++;
        }
        while (R>qu[i].first.second){
            freq2[freq[a[R]]]--;
            if (!freq2[freq[a[R]]]) have[freq[a[R]]]=0;
            freq[a[R]]--;
            if (freq[a[R]]&&!freq2[freq[a[R]]]) have[freq[a[R]]]=1;
            freq2[freq[a[R]]]++;
            R--;
        }
        while (L<qu[i].first.first){
            freq2[freq[a[L]]]--;
            if (!freq2[freq[a[L]]]) have[freq[a[L]]]=0;
            freq[a[L]]--;
            if (freq[a[L]]&&!freq2[freq[a[L]]]) have[freq[a[L]]]=1;
            freq2[freq[a[L]]]++;
            L++;
        }
        op[qu[i].second]=calcans();
    }
    for (int i=1; i<=q; i++) cout<<op[i]<<'\n';
}

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