제출 #1180078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180078		alexdd	Diversity (CEOI21_diversity)	C++17	64 / 100	7094 ms	4680 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int BUC = 550;
const int MAXV = 3e5;
int n,q;
int a[300005];
int fr[300005];
bool isbig[300005];
pair<pair<int,int>,int> qrys[300005];
int 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;
    return x.first.first < y.first.first;
}
int frfr[300005];
set<int> active;
void baga(int x)
{
    frfr[fr[x]]--;
    if(frfr[fr[x]]==0)
        active.erase(fr[x]);

    fr[x]++;

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

    fr[x]--;

    frfr[fr[x]]++;
    if(frfr[fr[x]]==1)
        active.insert(fr[x]);
}
int calc(int deja, int noi, int tot, int siz)
{
    int sum=0;
    for(int i=1;i<=noi;i++)
    {
        int le = deja + (i-1)*siz;
        int ri = tot - (deja + i*siz);
        sum += le*ri + siz*le + siz*ri;
    }
    return sum;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    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--;
        }

        int cntle=0,cntri=0,tot=0;
        //cerr<<"\n\n";
        for(auto it:active)
        {
            int noi = frfr[it];
            //cerr<<it<<" "<<noi<<" it & noi\n";
            tot += noi*(it*(it+1)/2);
            assert(noi > 0);
            //assert(abs(cntle-cntri)<=1);
            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;
            }
            //cerr<<cntle<<" "<<cntri<<" cntle & cntri\n";
        }
        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