Submission #1283103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283103		GoBananas69	Diversity (CEOI21_diversity)	C++20	38 / 100	7090 ms	8360 KiB

diversity

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
#include <vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
typedef long long ll;
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        unordered_map<int, int> freq;
        freq.reserve(r - l + 1);
        for (int i = l; i <= r; i++) freq[a[i]]++;

        int m = r - l + 1;
        int t = (int)freq.size();
        vector<int> blocks;
        for (auto &kv : freq) blocks.push_back(kv.second);

        sort(blocks.begin(), blocks.end(), greater<int>());

        ll L = 0, R = 0;
        ll placed = 0;

        deque<int> order;
        for (int s : blocks) {
            auto check = [&](bool right) -> pair<ll, deque<int>> {
                deque<int> tmp = order;
                if (right) tmp.push_back(s);
                else tmp.push_front(s);
                ll cur = 0;
                int S = 0;
                for (int x : tmp) S += x;
                int prefix = 0;
                for (int x : tmp) {
                    ll leftGap = prefix;
                    ll rightGap = S - x - prefix;
                    cur += leftGap * (leftGap + 1) / 2 + rightGap * (rightGap + 1) / 2;
                    prefix += x;
                }
                return {cur, tmp};
            };

            auto aRes = check(true);
            auto bRes = check(false);
            if (aRes.first >= bRes.first) {
                order = std::move(aRes.second);
            } else order = std::move(bRes.second);
        }

        ll totalSub = 1LL * m * (m + 1) / 2;
        ll sumGaps = 0;
        int S = 0;
        for (int x : order) S += x;
        int prefix = 0;
        for (int x : order) {
            ll leftGap = prefix;
            ll rightGap = S - x - prefix;
            sumGaps += leftGap * (leftGap + 1) / 2 + rightGap * (rightGap + 1) / 2;
            prefix += x;
        }
        ll ans = (ll)freq.size() * totalSub - sumGaps;
        cout << ans << "\n";
    }
    return 0;
}

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