제출 #1291878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291878		NValchanov	Diversity (CEOI21_diversity)	C++20	0 / 100	1 ms	568 KiB

diversity

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <deque>
#include <map>

using namespace std;

typedef long long llong;

const int MAXN = 3e5 + 10;

int n, q;
int a[MAXN];
map < int, int > cnt;
int maxa;

void read()
{
    cin >> n >> q;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];

        cnt[a[i]]++;
        maxa = max(maxa, a[i]);
    }
}

void solve()
{
    while(q--)
    {
        int left, right;
        cin >> left >> right;
    }

    vector < int > cnts;

    for(pair < int, int > p : cnt)
    {
        cnts.push_back(p.second);
    }

    sort(cnts.begin(), cnts.end());

    reverse(cnts.begin(), cnts.end());

    deque < int > dq;

    int sz = cnts.size();

    for(int i = 0; i < sz; i++)
    {
        if(i & 1)
        {
            dq.push_back(cnts[i]);
        }
        else
        {
            dq.push_front(cnts[i]);
        }
    }

    vector < int > suff(sz + 1, 0);

    for(int i = sz - 1; i >= 0; i--)
    {
        suff[i] = suff[i + 1] + dq[i];
    }

    llong ans = 0;
    llong div = 0;

    for(int i = 0; i < sz; i++)
    {
        div += 1LL * dq[i] * (i + 1);
    }

    for(int i = 0; i < sz; i++)
    {
        ans += 1LL * dq[i] * div;

        div -= suff[i];
    }

    for(int i = 0; i < sz; i++)
    {
        ans -= 1LL * dq[i] * (dq[i - 1]) / 2;
    }

    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();

    return 0;
}

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