Submission #492938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492938	2021-12-09T19:52:54 Z	blue	Diversity (CEOI21_diversity)	C++17	Compilation error	0 ms	0 KB

diversity

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

const int mx = 300'000;
const int mxQ = 50'000;
const int rt = 500;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define sz(x) (int(x.size()))

int N, Q;
vi a(1+mx);

vi l(1+mxQ), r(1+mxQ);
vll ans(1+mxQ);

int L = 1;
int R = 0;

vll ct(1+mx, 0);
vll freq(1+mx, 0);

vector<ll> sizes;
vector<bool> occ(1+mx, 0);

ll get_ans()
{
    vector<ll> sizes2;
    for(ll s: sizes)
    {
        if(occ[s]) continue;
        if(freq[s] == 0) continue;
        sizes2.push_back(s);
        occ[s] = 1;
    }
    sizes = sizes2;
    for(ll s: sizes) occ[s] = 0;

    sort(sizes.begin(), sizes.end(), [] (int u, int v)
    {
        return u > v;
    });

    deque< pair<ll, ll> > ord;
    int z = 0;
    for(ll s: sizes)
    {
        if(freq[s] % 2 == 1)
        {
            if(z) ord.push_back({s, 1});
            else ord.push_front({s, 1});
            z = !z;
        }

        if(freq[s]/2)
        {
            ord.push_back({s, freq[s]/2});
            ord.push_front({s, freq[s]/2});
        }
    }

    vll prefsum(1, 0);
    for(auto o: ord)
    {
        for(int y = 1; y <= o.second; y++)
        {
            prefsum.push_back(prefsum.back() + o.first);
        }
    }

    ll ans = 0;

    int P = sz(prefsum) - 1;

    for(int i = 1; i <= P; i++)
    {
        ans += ((prefsum[i] - prefsum[i-1])*(prefsum[i] - prefsum[i-1] + 1))/2;
        ans += (prefsum[i] - prefsum[i-1])*prefsum[i-1];
        ans += (prefsum[i] - prefsum[i-1])*(prefsum[P] - prefsum[i]);
        ans += (prefsum[P] - prefsum[i])*prefsum[i-1];
    }

    return ans;
}

void add_species(int a)
{
    freq[ct[a]]--;
    ct[a]++;
    freq[ct[a]]++;
    sizes.push_back(ct[a]);
}

void remove_species(int a)
{
    freq[ct[a]]--;
    ct[a]--;
    freq[ct[a]]++;
    sizes.push_back(ct[a]);
}

void expand_right()
{
    R++;
    add_species(a[R]);
}

void expand_left()
{
    L--;
    add_species(a[L]);
}

void contract_right()
{
    remove_species(a[R]);
    R--;
}

void contract_left()
{
    remove_species(a[L]);
    L++;
}

int main()
{
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int j = 1; j <= Q; j++) cin >> l[j] >> r[j];

    vi I(Q);
    for(int j = 0; j < Q; j++) I[j] = j+1;
    sort(I.begin(), I.end(), [] (int u, int v)
    {
        if(l[u]/rt != l[v]/rt) return l[u]/rt < l[v]/rt;
        else return r[u] < r[v];
    });

    freq[0] = mx;

    for(int q: I)
    {
        while(R < r[q]) expand_right();
        while(L > l[q]) expand_left();
        while(R > r[q]) contract_right();
        while(L < l[q]) contract_left();
        ans[q] = get_ans();
    }

    for(int q = 1; q <= Q; q++) cout << ans[q] << '\n';
}

Compilation message

diversity.cpp: In function 'll get_ans()':
diversity.cpp:43:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   43 |     sort(sizes.begin(), sizes.end(), [] (int u, int v)
      |     ^~~~
      |     qsort
diversity.cpp: In function 'int main()':
diversity.cpp:138:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
  138 |     sort(I.begin(), I.end(), [] (int u, int v)
      |     ^~~~
      |     qsort