Submission #859667

#	Time	Username	Problem	Language	Result	Execution time	Memory
859667		Tenis0206	Diversity (CEOI21_diversity)	C++11	100 / 100	1165 ms	377944 KiB

diversity

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5;
const int c = 150;
const int bsize = 550;

struct qry
{
    int st, dr, poz;
};

int n,q;
int v[nmax + 5];

int fr[nmax + 5];

int nrfr[nmax + 5];

int st[nmax + 5], dr[nmax + 5];

vector<int> l, h;

int sp[c + 5][nmax + 5];

vector<qry> B[bsize + 5];

bool sel[nmax + 5];

int sum_prod(int p, int st, int dr)
{
    if(st - p <= 0)
    {
        return sp[p][dr];
    }
    return sp[p][dr] - sp[p][st - p];
}

int solve_heavy(int x, int y)
{
    deque<int> d;
    for(int i=0; i<h.size(); i++)
    {
        if(i % 2 == 0)
        {
            d.push_back(h[i]);
        }
        else
        {
            d.push_front(h[i]);
        }
    }
    int sum_st = 0, sum_dr = 0;
    for(int i=1; i<=c; i++)
    {
        sum_st += st[i] * i;
        sum_dr += dr[i] * i;
    }
    for(auto it : d)
    {
        sum_dr += it;
    }
    int rez = 0;
    for(auto it : d)
    {
        sum_dr -= it;
        rez += 1LL * (y - x + 1) * (y - x + 2) / 2;
        rez -= 1LL * sum_st * (sum_st + 1) / 2;
        rez -= 1LL * sum_dr * (sum_dr + 1) / 2;
        sum_st += it;
    }
    return rez;
}

int solve_light(int x, int y)
{
    int rez = 0;

    int sum_dr = 0, sum_st = 0;
    for(int i=1; i<=c; i++)
    {
        sum_dr += dr[i] * i;
        sum_dr += st[i] * i;
    }
    for(auto it : h)
    {
        sum_dr += it;
    }
    for(int i=1; i<=c; i++)
    {
        int cnt = st[i];
        if(cnt)
        {
            rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt;
            rez -= sum_prod(i, sum_st, sum_st + i * (cnt - 1));
            rez -= sum_prod(i, sum_dr - i * cnt, sum_dr - i);
            sum_st += st[i] * i;
            sum_dr -= st[i] * i;
        }
    }

    sum_dr = 0, sum_st = 0;
    for(int i=1; i<=c; i++)
    {
        sum_st += st[i] * i;
        sum_st += dr[i] * i;
    }
    for(auto it : h)
    {
        sum_st += it;
    }
    for(int i=1; i<=c; i++)
    {
        int cnt = dr[i];
        if(cnt)
        {
            rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt;
            rez -= sum_prod(i, sum_st - i * cnt, sum_st - i);
            rez -= sum_prod(i, sum_dr, sum_dr + i * (cnt - 1));
            sum_st -= dr[i] * i;
            sum_dr += dr[i] * i;
        }
    }

    return rez;
}

int query(int x, int y)
{
    int nr = h.size();
    for(int i=c; i>=1; i--)
    {
        if(nrfr[i]==0)
        {
            st[i] = dr[i] = 0;
            continue;
        }
        if(nrfr[i] % 2 == 0)
        {
            st[i] = dr[i] = nrfr[i] / 2;
        }
        else
        {
            if(nr % 2 == 0)
            {
                st[i] = nrfr[i] / 2;
                dr[i] = nrfr[i] / 2 + 1;
            }
            else
            {
                st[i] = nrfr[i] / 2 + 1;
                dr[i] = nrfr[i] / 2;
            }
        }
        nr += nrfr[i];
    }
    int rez = 0;
    rez += solve_heavy(x,y);
    rez += solve_light(x,y);
    return rez;
}

void Add(int val)
{
    --nrfr[fr[val]];
    ++fr[val];
    ++nrfr[fr[val]];
    if(fr[val] == c + 1 && !sel[val])
    {
        l.push_back(val);
        sel[val] = true;
    }
}

void Remove(int val)
{
    --nrfr[fr[val]];
    --fr[val];
    ++nrfr[fr[val]];
}

void build_h()
{
    vector<int> aux;
    h.clear();
    for(auto it : l)
    {
        if(fr[it] > c)
        {
            aux.push_back(it);
            h.push_back(fr[it]);
        }
    }
    for(auto it : l)
    {
        sel[it] = false;
    }
    l = aux;
    for(auto it : l)
    {
        sel[it] = true;
    }
    sort(h.begin(),h.end(),greater<int>());
}

void precalc()
{
    for(int p=1; p<=c; p++)
    {
        for(int i=1; i<=n; i++)
        {
            sp[p][i] = 1LL * i * (i + 1) / 2;
            if(i - p > 0)
            {
                sp[p][i] += sp[p][i - p];
            }
        }
    }
}

int get_bucket(int poz)
{
    return (poz - 1) / bsize + 1;
}

bool cmp(qry a, qry b)
{
    return (a.dr < b.dr);
}

int rez[nmax + 5];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    precalc();
    for(int i=1; i<=q; i++)
    {
        qry x;
        cin>>x.st>>x.dr;
        x.poz = i;
        int bucket = get_bucket(x.st);
        B[bucket].push_back(x);
    }
    for(int b=1; b<=bsize+1; b++)
    {
        if(!B[b].size())
        {
            continue;
        }
        nrfr[0] = n;
        l.clear();
        for(int i=1; i<=nmax; i++)
        {
            nrfr[i] = 0;
            fr[i] = 0;
            sel[i] = false;
        }
        sort(B[b].begin(), B[b].end(),cmp);
        int last_st = B[b].front().st, last_dr = B[b].front().st - 1;
        for(auto it : B[b])
        {
            int st = it.st;
            int dr = it.dr;
            int poz = it.poz;
            for(int i=last_dr+1; i<=dr; i++)
            {
                Add(v[i]);
            }
            if(last_st < st)
            {
                for(int i=last_st; i<st; i++)
                {
                    Remove(v[i]);
                }
            }
            else
            {
                for(int i=st; i<last_st; i++)
                {
                    Add(v[i]);
                }
            }
            build_h();
            rez[poz] = query(st,dr);
            last_st = st, last_dr = dr;
        }
    }
    for(int i=1; i<=q; i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'long long int solve_heavy(long long int, long long int)':
diversity.cpp:44:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0; i<h.size(); i++)
      |                  ~^~~~~~~~~

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