Submission #1283104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283104		GoBananas69	Diversity (CEOI21_diversity)	C++20	64 / 100	292 ms	20212 KiB

diversity

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#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")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MAXN = 3e5 + 5;
const ll MAXQ = 5e4 + 5;
const ll MAX = 1e18;

ll n, q, k = 0, ans = MAX;
ll cnt[MAXN], compressed[MAXN], ccnt[MAXN];
vector<ll> nums;
set<ll> st;

ll count(ll iniIdx, ll sum[]) {
    ll out = 0, bef = 0;
    for (int i = iniIdx; i <= k; i += 2) {
        ll after = sum[(iniIdx + 1) % 2] + (sum[iniIdx % 2] - bef - ccnt[i]);
        out += bef * bef + after * after;
        bef += ccnt[i];
    }

    return out;
}

ll calc() {
    ll out = n * k * (n + 1) - n * (k - 1);
    ll sqSum = 0;

    sort(ccnt + 1, ccnt + k + 1);

    ll sum[2] = {0, 0};

    for (int i = 1; i <= k; ++i) {
        sum[i % 2] += ccnt[i];
    }

    sqSum += count(1, sum);
    sqSum += count(2, sum);

    out = (out - sqSum) / 2;
    return out;
}

void compress() {
    for (auto it = st.begin(); it != st.end(); it++) {
        k++;
        compressed[(*it)] = k;
        ccnt[k] = cnt[(*it)];
    }
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        ll tmp;
        cin >> tmp;
        st.insert(tmp);
        cnt[tmp]++;
    }

    compress();

    ll _tmp;
    cin >> _tmp >> _tmp;

    for (int i = 1; i <= k; ++i) {
        nums.push_back(i);
    }

    sort(nums.begin(), nums.end());

    ans = calc();

    cout << ans << "\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