Submission #1180103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180103		alexdd	Diversity (CEOI21_diversity)	C++17	64 / 100	7094 ms	5040 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
const int BUC = 900;
int n,q;
int a[300005];
int fr[300005];
pair<pair<int,int>,int> qrys[300005];
long long rez[300005];
bool cmp(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)
{
    if(x.first.second / BUC != y.first.second / BUC)
        return x.first.second < y.first.second;
    if((x.first.second / BUC) % 2 == 0)
        return x.first.first < y.first.first;
    else
        return x.first.first > y.first.first;
}
map<int,int> frfr;
void baga(int x)
{
    frfr[fr[x]]--;
    if(frfr[fr[x]]==0)
        frfr.erase(fr[x]);

    fr[x]++;

    frfr[fr[x]]++;
}
void scoate(int x)
{
    frfr[fr[x]]--;
    if(frfr[fr[x]]==0)
        frfr.erase(fr[x]);

    fr[x]--;

    frfr[fr[x]]++;
}
long long prec[300005];
long long calc(long long deja, long long noi, long long tot, long long siz)
{
    long long sum=0;
    sum += noi * (deja*tot - deja*deja - siz*siz);
    sum += noi*(noi+1)/2 * (-deja*siz + siz*tot);
    sum += noi*(noi-1)/2 * (-deja*siz);
    sum -= prec[noi]*siz*siz;
    return sum;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(long long i=2;i<=n;i++)
        prec[i] = prec[i-1] + i*(i-1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=q;i++)
    {
        cin>>qrys[i].first.first>>qrys[i].first.second;
        qrys[i].second = i;
    }
    sort(qrys+1,qrys+1+q,cmp);
    int cle=1,cri=0;
    for(int pas=1;pas<=q;pas++)
    {
        int qle = qrys[pas].first.first, qri = qrys[pas].first.second, qid = qrys[pas].second;
        while(cri < qri)
        {
            cri++;
            baga(a[cri]);
        }
        while(cle > qle)
        {
            cle--;
            baga(a[cle]);
        }

        while(cle < qle)
        {
            scoate(a[cle]);
            cle++;
        }
        while(cri > qri)
        {
            scoate(a[cri]);
            cri--;
        }

        long long cntle=0,cntri=0,tot=0;
        for(auto x:frfr)
        {
            long long it = x.first;
            long long noi = x.second;
            if(noi<=0)
                continue;
            tot += noi*(it*(it+1)/2);
            assert(noi > 0);
            if(cntle <= cntri)
            {
                tot += calc(cntle, (noi+1)/2, qri-qle+1, it);
                tot += calc(cntri, noi/2, qri-qle+1, it);

                cntle += ((noi+1)/2)*it;
                cntri += (noi/2)*it;
            }
            else
            {
                tot += calc(cntri, (noi+1)/2, qri-qle+1, it);
                tot += calc(cntle, noi/2, qri-qle+1, it);

                cntri += ((noi+1)/2)*it;
                cntle += (noi/2)*it;
            }
        }
        rez[qid] = tot;
    }
    for(int i=1;i<=q;i++)
        cout<<rez[i]<<"\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