Submission #858350

#	Time	Username	Problem	Language	Result	Execution time	Memory
858350		danikoynov	Diversity (CEOI21_diversity)	C++14	4 / 100	14 ms	5212 KiB

diversity

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 3e5 + 10, maxq = 5e4 + 10;
const int block_size = sqrt(maxn);

struct query
{
    int l, r, idx;
}task[maxq];

bool cmp_mo(query t1, query t2)
{
    if (t1.l / block_size == t2.l / block_size)
        return t1.r < t2.r;
    return t1.l < t2.l;
}

int n, q, a[maxn], freq[maxn], comp[maxn];

void update(int val, int c)
{
    ///cout << "update " << val << " " << c << endl;
    comp[freq[val]] --;
    freq[val] += c;
    comp[freq[val]] ++;
}

int lf = 1, rf = 0, ans[maxn];
void move_borders(int left, int right)
{
    while(rf < right)
    {
        rf ++;
        update(a[rf], 1);
    }

    while(lf > left)
    {
        lf --;
        update(a[lf], 1);
    }

    while(rf > right)
    {
        update(a[rf], -1);
        rf --;
    }

    while(lf < left)
    {
        update(a[lf], -1);
        lf ++;
    }
}

ll arr[maxn], bef[maxn], aft[maxn];
ll calc_function()
{
    vector < ll > values;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < comp[i]; j ++)
        values.push_back(i);


    int sz = values.size(), pt = 0;

    for (int i = 0; i < sz; i += 2)
    {
        arr[++ pt] = values[i];
    }
    int f = sz - 1;
    if (sz % 2 == 1)
        f --;
    for (int i = f; i >= 0; i -= 2)
        arr[++ pt] = values[i];



    /**for (int i = 1; i <= n; i ++)
        cout << comp[i] << " ";
    cout << endl;*/
    ll bf = 0, tot = 0;
    for (int i = 1; i <= sz; i ++)
    {
        bef[i] = bf;
        bf += arr[i];
    }
    ll af = 0;
    for (int i = sz ; i > 0; i --)
    {
        aft[i] = af;
        af += arr[i];
    }

    for (ll i = 1; i <= sz; i ++)
    {
        tot = tot + i * arr[i] * (bef[i] - aft[i]);
    }

    ll sf = 0;
    for (int i = 1; i <= sz; i ++)
    {
        ll cur = arr[i];
        tot = tot + cur * (cur + 1) / 2;
        tot = tot + arr[i] * sf;
        sf += arr[i];
    }
    return tot;

}

void compress_data()
{
    int cur = 0;
    map < int, int > mp;
    for (int i = 1; i <= n; i ++)
    {
        if (mp[a[i]] == 0)
            mp[a[i]] = ++ cur;
        a[i] = mp[a[i]];
    }
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    compress_data();
    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
    }

    sort(task + 1, task + q + 1, cmp_mo);

    for (int i = 1; i <= q; i ++)
    {
        move_borders(task[i].l, task[i].r);
        ans[task[i].idx] = calc_function();
    }

    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;

}

int main()
{
    solve();
    return 0;
}

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