Submission #492931

#	Time	Username	Problem	Language	Result	Execution time	Memory
492931		blue	Diversity (CEOI21_diversity)	C++17	0 / 100	2 ms	1484 KiB

diversity

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

using ll = long long;

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<int> ct(1+300'000, 0);
    for(int i = 1; i <= N; i++)
    {
        int a;
        cin >> a;
        ct[a]++;
    }

    int l, r;
    cin >> l >> r;

    vector<ll> val;
    for(int f = 1; f <= 300'000; f++)
        if(ct[f])
            val.push_back(ct[f]);

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

    deque<ll> val2;
    for(int i = 0; i < int(val.size()); i++)
    {
        if(i % 2 == 0) val2.push_back(val[i]);
        else val2.push_front(val[i]);
    }
    val2.push_front(0);

    int G = int(val2.size()) - 1;

    vector<ll> prefsum(1+G, 0);
    for(int i = 1; i <= G; i++) prefsum[i] = prefsum[i-1] + val2[i];

    // for(int f = 1; f <= G; f++) cerr << val2[f] << ' ';
    // cerr << '\n';

    ll res = 0;
    for(int i = 1; i <= G; i++)
    {
        res += (val2[i]*(val2[i]+1))/2 + prefsum[i-1]*val2[i] + (prefsum[G] - prefsum[i])*val2[i] + (prefsum[i-1])*(prefsum[G] - prefsum[i]);
        // cerr << "!\n";
        // cerr << (prefsum[G] - prefsum[i])*val2[i] << '\n';
        // cerr << (val2[i]*(val2[i]+1))/2 << '\n';
        // cerr << prefsum[i-1]*val2[i] << '\n';
        // cerr << (prefsum[i-1])*(prefsum[G] - prefsum[i]) << '\n';
        // cerr << i << " : " << (val2[i]*(val2[i]+1))/2 + prefsum[i-1]*val2[i] + (prefsum[G] - prefsum[i])*val2[i] * (prefsum[i-1])*(prefsum[G] - prefsum[i]);
        // cerr << '\n';
    }

    cout << res << '\n';
}

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