Submission #531546

#	Time	Username	Problem	Language	Result	Execution time	Memory
531546		eecs	Diversity (CEOI21_diversity)	C++17	100 / 100	6797 ms	7180 KiB

diversity

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int maxn = 300010, SZ = 500;
int n, q, a[maxn], bel[maxn], occ[maxn], cnt[maxn];
long long ans[maxn];
vector<array<int, 3>> Q;
unordered_set<int> S;

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]), bel[i] = (i - 1) / SZ + 1;
    }
    for (int i = 1, l, r; i <= q; i++) {
        scanf("%d %d", &l, &r);
        Q.push_back({l, r, i});
    }
    sort(Q.begin(), Q.end(), [&](array<int, 3> p, array<int, 3> q) {
        if (bel[p[0]] ^ bel[q[0]]) return bel[p[0]] < bel[q[0]];
        return bel[p[0]] & 1 ? p[1] < q[1] : p[1] > q[1];
    });
    cnt[0] = maxn, S.insert(0);
    auto ins = [&](int x, int coef) {
        if (!--cnt[occ[x]]) S.erase(occ[x]);
        occ[x] += coef;
        if (!cnt[occ[x]]++) S.insert(occ[x]);
    };
    int l = 1, r = 0;
    for (auto &p : Q) {
        while (l > p[0]) ins(a[--l], 1);
        while (r < p[1]) ins(a[++r], 1);
        while (l < p[0]) ins(a[l++], -1);
        while (r > p[1]) ins(a[r--], -1);
        vector<pair<int, int>> V;
        long long s = 0;
        int all = 0;
        for (int x : S) if (x) {
            V.emplace_back(x, cnt[x]), all += cnt[x];
            s += 1LL * x * x * cnt[x], ans[p[2]] += 1LL * x * (x + 1) / 2 * cnt[x];
        }
        sort(V.begin(), V.end());
        ans[p[2]] += (1LL * (r - l + 1) * (r - l + 1) - s) / 2;
        int pl = 1, pr = all, ls = 0, rs = 0;
        for (auto &q : V) {
            while (q.second--) {
                if (pl <= all - pr) {
                    ans[p[2]] += 1LL * pl * q.first * (2 * ls + q.first - (r - l + 1));
                    pl++, ls += q.first;
                } else {
                    ans[p[2]] += 1LL * pr * q.first * (r - l + 1 - 2 * rs - q.first);
                    pr--, rs += q.first;
                }
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
diversity.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d", &a[i]), bel[i] = (i - 1) / SZ + 1;
      |         ~~~~~^~~~~~~~~~~~~
diversity.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d %d", &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