Submission #657535

#	Time	Username	Problem	Language	Result	Execution time	Memory
657535		dooompy	Diversity (CEOI21_diversity)	C++17	100 / 100	1785 ms	22320 KiB

diversity

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

const int block = 550;

#define int ll

ll a[300005];
map<int, ll> ct;

struct query {
    int l, r, i;

    bool operator<(query o ) const {
        if (l / block == o.l / block) {
            return (l / block & 1) ? r > o.r : r < o.r;
        }
        return l / block < o.l / block;
    }
};

int freq[300005];
int cnt[300005];
bool in[300005];

vector<int> arr;

void change(int val, int amt) {
    cnt[freq[val]]--;

    freq[val] += amt;

    if (cnt[freq[val]] == 0 && !in[freq[val]]) {
        cnt[freq[val]]++;
        in[freq[val]] = true;
        arr.push_back(freq[val]);
    } else {
        cnt[freq[val]]++;
    }
}

ll printout[200005];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, q; cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ct[a[i]]++;
    }

    vector<query> queries;

    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        queries.push_back({l, r, i});
    }

    sort(queries.begin(), queries.end());
    int l = 1, r = 0;

    for (auto [ql, qr, i] : queries) {
        while (l > ql) change(a[--l], 1);
        while (r < qr) change(a[++r], 1);
        while (l < ql) change(a[l++], -1);
        while (r > qr) change(a[r--], -1);

        vector<int> upd;
        for (auto cur : arr) {
            if (cnt[cur] == 0) {
                in[cur] = false;
            } else upd.push_back(cur);
        }

        arr = upd;

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

        vector<pair<ll, ll>> front, back;
        int ctf = 0, ctb = 0;
        for (auto cur : arr) {
            int sz = cnt[cur];

            int more = (sz  + 1) / 2, less = sz - more;

            if (ctf > ctb) {
                back.push_back({cur, more});
                if (less != 0) front.push_back({cur, less});

                ctb += more * cur;
                ctf += less * cur;
            } else {
                if (less != 0) back.push_back({cur, less});
                front.push_back({cur, more});

                ctb += less * cur;
                ctf += more * cur;
            }
        }
        
        reverse(back.begin(), back.end());

        for (auto t : back) front.push_back(t);

        ll pref = 0, n = r - l + 1, ans = 0;
        for (auto [s, k] : front) {
            ans += (k * (pref * s + pref * s * k) / 2);
            ll suff = n - pref - s * k;
            ans += (k * (suff * s + suff * s * k) / 2);

            ans += (pref * suff * k);

            ans += s * (s - 1) / 2 * k;

            ans += k * ((k - 1) * (s * s * 2 + (k) * s * s)) / 2;

            ans -= (s * s * 2 * (k - 1) * (k) * (k + 1)) / 6;

            pref += s * k;
        }

        printout[i] = ans + n;
    }

    for (int i = 0; i < q; i++) {
        cout << printout[i] << "\n";
    }

}

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