Submission #858360

#	Time	Username	Problem	Language	Result	Execution time	Memory
858360		danikoynov	Diversity (CEOI21_diversity)	C++14	64 / 100	7008 ms	22964 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 = 200;

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 q, a[maxn], freq[maxn], comp[maxn];
ll n;
unordered_multiset < int > act;
void update(int val, int c)
{
    ///cout << "update " << val << " " << c << endl;
    if (freq[val] != 0)
    act.erase(act.find(freq[val]));
    ///comp[freq[val]] --;
    freq[val] += c;
    ///comp[freq[val]] ++;
    if (freq[val] != 0)
    act.insert(freq[val]);
}

int lf = 1, rf = 0;
ll 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(ll len)
{
    vector < ll > values;
    for (int cur : act)
        values.push_back(cur);
    sort(values.begin(), values.end());
    /**for (int i = 1; i <= n; i ++)
        for (int j = 0; j < comp[i]; j ++)
        values.push_back(i);*/
    /**for (int cur : values)
        cout << cur << " ";
    cout << endl;*/

    ll sz = values.size();
    int 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 tot = 0, pref = 0;
    for (int i = 1; i < sz; i ++)
    {
        pref += arr[i];
        tot = tot + pref * pref;
    }
    ll suff = 0;
    for (int i = sz; i > 1; i --)
    {
        suff = suff + arr[i];
        tot = tot + suff * suff;
    }

    ///cout << tot << endl;
    tot = (sz * len * (len + 1) - len * (sz - 1) - tot) / 2;
    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(task[i].r - task[i].l + 1);
    }

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

}

int main()
{
    speed();
    solve();
    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