Submission #589915

#	Time	Username	Problem	Language	Result	Execution time	Memory
589915		alextodoran	Diversity (CEOI21_diversity)	C++17	100 / 100	6456 ms	5776 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];
unordered_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 () {
    vector <pair <int, int>> v;
    for (pair <int, int> p : mp) {
        v.push_back(p);
    }
    sort(v.begin(), v.end(), greater <pair <int, int>> ());
    int sum = 0, cnt = 0;
    ll sumLR = 0, sumRL = 0;
    ll X = 0, Y = 0;
    for (pair <int, int> p : v) {
        int len, occ; tie(len, occ) = p;

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

        for (char c : {'L', 'R'}) {
            ll sum1L = (ll) L * (L - 1) / 2, sum2L = (ll) L * (L - 1) * (2 * L - 1) / 6;
            Y += len * (sumRL * L + (ll) len * cnt * sum1L + len * (sum2L - sum1L) / 2);
            ll aux = 0;
            aux += (ll) sum * sum * L;
            aux += (ll) 2 * sum * len * sum1L;
            aux += (ll) len * len * sum2L;
            aux -= X * L + (ll) len * len * sum1L;
            aux /= 2;
            Y += aux;
            X += (ll) len * len * L;
            sumLR += (ll) sum * L + len * sum1L;
            sumRL += (ll) len * cnt * L + len * sum1L;
            sum += (ll) len * L;
            cnt += L;
            swap(L, R);
            swap(sumLR, sumRL);
        }

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

ll answer[Q_MAX + 2];

mt19937 rnd (13);
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;
}

Compilation message (stderr)

diversity.cpp: In function 'll solve()':
diversity.cpp:61:19: warning: unused variable 'c' [-Wunused-variable]
   61 |         for (char c : {'L', 'R'}) {
      |                   ^

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