Submission #589832

#	Time	Username	Problem	Language	Result	Execution time	Memory
589832		alextodoran	Diversity (CEOI21_diversity)	C++17	64 / 100	66 ms	4572 KiB

diversity

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 300000;

int N, Q;
int A[N_MAX + 2];

ll solve (map <int, int> &mp) {
    int sum = 0, cnt = 0;
    ll sumLR = 0, sumRL = 0;
    ll X = 0, Y = 0;
    for (map <int, int> :: reverse_iterator it = mp.rbegin(); it != mp.rend(); it++) {
        int len, occ; tie(len, occ) = *it;
        for (int i = 1; i <= occ; i++) {
            if (sumLR < sumRL) {
                Y += sumRL * len + ((ll) sum * sum - X) / 2;
                X += (ll) len * len;
                sumLR += sum;
                sumRL += (ll) len * cnt;
                sum += len;
                cnt += 1;
            } else {
                Y += sumLR * len + ((ll) sum * sum - X) / 2;
                X += (ll) len * len;
                sumRL += sum;
                sumLR += (ll) len * cnt;
                sum += len;
                cnt += 1;
            }
        }
    }
    ll ret = (cnt - 1) * X + 2 * Y;
    ret += (ll) sum * (cnt - 1);
    ret /= 2;
    return ret;
}

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

    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    sort(A + 1, A + N + 1);

    vector <int> v;
    for (int i = 1; i <= N; i++) {
        if (A[i] == A[i - 1]) {
            v.back()++;
        } else {
            v.push_back(1);
        }
    }

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

    map <int, int> mp;
    for (int len : v) {
        mp[len]++;
    }
    cout << (ll) (int) v.size() * N * (N + 1) / 2 - solve(mp) << "\n";

    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