제출 #1167344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167344		thinknoexit	Diversity (CEOI21_diversity)	C++20	64 / 100	47 ms	8124 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 300300;
int a[N];
ll qs[N];
int cnt[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    while (q--) { int __; cin >> __ >> __; }
    vector<pair<int, int>> v;
    for (int i = 1;i <= 300000;i++) {
        if (cnt[i]) v.push_back({ cnt[i], i });
    }
    sort(v.begin(), v.end());
    deque<int> f, b;
    for (auto& [w, x] : v) {
        if (f.size() < b.size()) {
            for (int j = 1;j <= w;j++) f.push_back(x);
        }
        else {
            for (int j = 1;j <= w;j++) b.push_front(x);
        }
    }
    int idx = 0;
    for (int i = 0;i < (int)f.size();i++) {
        a[++idx] = f[i];
    }
    for (int i = 0;i < (int)b.size();i++) {
        a[++idx] = b[i];
    }
    ll ans = 1ll * n * (n + 1) / 2;
    for (int i = 1;i <= n;i++) {
        qs[i] = qs[i - 1] + (a[i] != a[i - 1]);
        ans += qs[i] * (2 * i - 1 - n);
    }
    cout << ans << '\n';
    //  1  1 1 2
    //  1  2 2 2
    // -3 -1 1 3
    //  1  1 1 2 2
    //  1  1 2 2 2
    // -4 -2 0 2 4
    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