Submission #858400

#	Time	Username	Problem	Language	Result	Execution time	Memory
858400		danikoynov	Diversity (CEOI21_diversity)	C++14	100 / 100	2000 ms	22736 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 q, a[maxn], freq[maxn], comp[maxn];
ll n;
///unordered_map < int, int > act;
int act[maxn];
bitset < maxn > bt;
void update(int val, int c)
{

    ///cout << "update " << val << " " << c << endl;
    if (freq[val] != 0)
    {
        act[freq[val]] --;
        if (act[freq[val]] == 0)
            bt[freq[val]] = 0;
    }

    ///comp[freq[val]] --;
    freq[val] += c;
    ///comp[freq[val]] ++;
    if (freq[val] != 0)
    {
        act[freq[val]] ++;
        bt[freq[val]] = 1;
    }
}

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], prec[maxn];
ll calc_function(ll len)
{
    vector < pair < ll, ll >  > values;
    int bit = bt._Find_first();
    while(bit < maxn)
    {
        values.push_back({bit, act[bit]});
        bit = bt._Find_next(bit);
    }
    /**
    for (pair < int, int > cur : act)
    {
        values.push_back(cur);
    }
    sort(values.begin(), values.end());*/

    ll sz = values.size(), cp = 0;
    deque < pair < ll, ll > > dq;
    ll left_add = 0, right_add = 0;
    values.back().second --;
    cp ++;
    dq.push_back({values.back().first, 1});
    for (int i = sz - 1; i >= 0; i --)
    {
        ll p1 = (values[i].second + 1) / 2;
        ll p2 = (values[i].second) / 2;
        if (right_add > left_add)
            swap(p1, p2);
        if(p1 != 0)
            dq.push_back({values[i].first, p1});
        if (p2 != 0)
            dq.push_front({values[i].first, p2});

        cp += values[i].second;
        left_add += p2;
        right_add += p1;
    }


    ll tot = 0, pref = 0;
    for (int i = 0; i < dq.size(); i ++)
    {
        ll l = dq[i].second;
        tot = tot + l * pref * pref;
        tot = tot + l * (l + 1) * pref * dq[i].first;
        tot = tot + prec[l] * dq[i].first * dq[i].first;
        pref = pref + dq[i].first * l;
        ///cout << pref << " " << tot << " " << dq[i].first << " " << dq[i].second << endl;
    }
    tot = tot - pref * pref;

    ll suff = 0;
    for (int i = dq.size() - 1; i >= 0; i --)
    {
        ll l = dq[i].second;
        tot = tot + l * suff * suff;
        tot = tot + l * (l + 1) * suff * dq[i].first;
        tot = tot + prec[l] * dq[i].first * dq[i].first;
        suff = suff + dq[i].first * l;
    }
    tot = tot - suff * suff;

    tot = (cp * len * (len + 1) - len * (cp - 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];
    for (int i = 1; i <= n; i ++)
    {
        prec[i] = prec[i - 1] + (ll)(i) * (ll)(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();
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'll calc_function(ll)':
diversity.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < dq.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