Submission #589901

#	Time	Username	Problem	Language	Result	Execution time	Memory
589901		alextodoran	Diversity (CEOI21_diversity)	C++17	64 / 100	7057 ms	4344 KiB

diversity

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

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 300000;
const int A_MAX = 300000;
const int Q_MAX = 50000;

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

int bucketSize;

struct Query {
    int l, r;
    int id;
};
bool operator < (const Query &a, const Query &b) {
    return make_pair((a.l - 1) / bucketSize, a.r) < make_pair((b.l - 1) / bucketSize, b.r);
}

Query queries[Q_MAX + 2];

int occ[A_MAX + 2];
map <int, int> mp;

void update (int val, int sgn) {
    if (--mp[occ[val]] == 0) {
        mp.erase(occ[val]);
    }
    occ[val] += sgn;
    mp[occ[val]]++;
}

ll solve () {
    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;
    ret = cnt * sum * (sum + 1) / 2 - ret;
    return ret;
}

ll answer[Q_MAX + 2];

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];
    }
    bucketSize = max(1, (int) (N / sqrt(Q)));
    for (int i = 1; i <= Q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    sort(queries + 1, queries + Q + 1);

    int l = 1, r = 0;
    for (int i = 1; i <= Q; i++) {
        while (queries[i].l < l) {
            update(A[--l], +1);
        }
        while (r < queries[i].r) {
            update(A[++r], +1);
        }
        while (l < queries[i].l) {
            update(A[l++], -1);
        }
        while (queries[i].r < r) {
            update(A[r--], -1);
        }
        answer[queries[i].id] = solve();
    }
    for (int i = 1; i <= Q; i++) {
        cout << answer[i] << "\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