Submission #797986

#	Time	Username	Problem	Language	Result	Execution time	Memory
797986		finn__	Diversity (CEOI21_diversity)	C++17	64 / 100	29 ms	3412 KiB

diversity

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 300000;

uint32_t a[N];

template <typename T>
inline T gauss(T n) { return (n * (n + 1)) / 2; }

template <typename T>
inline T range_gauss(T a, T b)
{
    return gauss(b) - (a ? gauss(a - 1) : 0);
}

uint64_t get_cost(size_t n, size_t l, size_t r)
{
    return (r + 1) * n - l * l - range_gauss(l, r);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, q, m = 0;
    cin >> n >> q;

    for (size_t i = 0; i < n; ++i)
    {
        size_t x;
        cin >> x;
        a[x - 1]++;
        m = max(m, x);
    }
    sort(a, a + m);

    uint64_t lsum = 0, rsum = 0, cost = 0;
    for (size_t i = 0; i < m; ++i)
        if (lsum < rsum)
        {
            cost += get_cost(n, lsum, lsum + a[i] - 1);
            lsum += a[i];
        }
        else
        {
            cost += get_cost(n, n - rsum - a[i], n - rsum - 1);
            rsum += a[i];
        }

    cout << cost << '\n';
}

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