Submission #589895

#	Time	Username	Problem	Language	Result	Execution time	Memory
589895		alextodoran	Diversity (CEOI21_diversity)	C++17	64 / 100	58 ms	4556 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) {
    ll 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++) {
        ll len, occ; tie(len, occ) = *it;

        ll u = sumRL - sumLR + sum * occ; ll v = (2 * sum);
        ll L = (v == 0 ? 0 : (u >= 0 ? u / v : -(-u / v)));
        L = max(L, (ll) 0); L = min(L, occ - 1);
        ll R = (occ - 1) - L;

        ll aux;
        // place L to the left
        Y += len * (sumRL * L + len * cnt * L * (L - 1) / 2 + len * (L * (L - 1) * (2 * L - 1) / 6 - L * (L - 1) / 2) / 2);
        aux = 0;
        aux += sum * sum * L;
        aux += 2 * sum * len * L * (L - 1) / 2;
        aux += len * len * L * (L - 1) * (2 * L - 1) / 6;
        aux -= X * L + len * len * L * (L - 1) / 2;
        aux /= 2;
        Y += aux;
        X += len * len * L;
        sumLR += sum * L + len * L * (L - 1) / 2;
        sumRL += len * cnt * L + len * L * (L - 1) / 2;
        sum += len * L;
        cnt += L;
        // place R to the right
        Y += len * (sumLR * R + len * cnt * R * (R - 1) / 2 + len * (R * (R - 1) * (2 * R - 1) / 6 - R * (R - 1) / 2) / 2);
        aux = 0;
        aux += sum * sum * R;
        aux += 2 * sum * len * R * (R - 1) / 2;
        aux += len * len * R * (R - 1) * (2 * R - 1) / 6;
        aux -= X * R + len * len * R * (R - 1) / 2;
        aux /= 2;
        Y += aux;
        X += len * len * R;
        sumRL += sum * R + len * R * (R - 1) / 2;
        sumLR += len * cnt * R + len * R * (R - 1) / 2;
        sum += len * R;
        cnt += R;

        if (sumLR < sumRL) {
            Y += sumRL * len + (sum * sum - X) / 2;
            X += len * len;
            sumLR += sum;
            sumRL += len * cnt;
            sum += len;
            cnt += 1;
        } else {
            Y += sumLR * len + (sum * sum - X) / 2;
            X += len * len;
            sumRL += sum;
            sumLR += 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