Submission #475569

#	Time	Username	Problem	Language	Result	Execution time	Memory
475569		flashmt	Diversity (CEOI21_diversity)	C++17	100 / 100	4981 ms	6752 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
const int A = 3e5;
const int K = 1000;

inline long long getSum(int x)
{
  return x * (x + 1LL) / 2;
}

long long calc(vector<int> &smallCnt, map<int, int> &bigCnt, int sumAll)
{
  int side = 0;
  long long sum[2] = {0}, res = 0;

  auto go = [&](int k, int v)
  {
    int x = (v + 1) / 2, y = v / 2;

    res += 1LL * x * (sumAll - sum[side]) * sum[side] + getSum(x) * k * (sumAll - sum[side]);
    res -= getSum(x - 1) * k * sum[side] + (x - 1LL) * x * (x + 1) / 3 * k * k;
    res -= getSum(k - 1) * x;
    sum[side] += x * k;

    if (y)
    {
      res += 1LL * y * (sumAll - sum[side ^ 1]) * sum[side ^ 1] + getSum(y) * k * (sumAll - sum[side ^ 1]);
      res -= getSum(y - 1) * k * sum[side ^ 1] + (y - 1LL) * y * (y + 1) / 3 * k * k;
      res -= getSum(k - 1) * y;
      sum[side ^ 1] += y * k;
    }

    side ^= v % 2;
  };

  for (int i = 1; i < K; i++)
    if (smallCnt[i])
      go(i, smallCnt[i]);
  for (auto [k, v] : bigCnt)
    go(k, v);

  return res;
}

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

  vector<int> id(q);
  iota(begin(id), end(id), 0);
  auto cmp = [&](int u, int v)
  {
    if (l[u] / K != l[v] / K)
      return l[u] < l[v];
    return l[u] / K & 1 ? r[u] < r[v] : r[u] > r[v];
  };
  sort(begin(id), end(id), cmp);

  vector<int> cnt(A), smallCnt(K);
  map<int, int> bigCnt;

  auto add = [&](int x)
  {
    if (cnt[x] < K) smallCnt[cnt[x]]--;
    else if (!--bigCnt[cnt[x]]) bigCnt.erase(cnt[x]);
    cnt[x]++;
    if (cnt[x] < K) smallCnt[cnt[x]]++;
    else bigCnt[cnt[x]]++;
  };

  auto remove = [&](int x)
  {
    if (cnt[x] < K) smallCnt[cnt[x]]--;
    else if (!--bigCnt[cnt[x]]) bigCnt.erase(cnt[x]);
    cnt[x]--;
    if (cnt[x] < K) smallCnt[cnt[x]]++;
    else bigCnt[cnt[x]]++;
  };

  vector<long long> ans(q);
  int curL = 0, curR = -1;
  for (int i : id)
  {
    while (curL > l[i])
      add(a[--curL]);
    while (curR < r[i])
      add(a[++curR]);
    while (curL < l[i])
      remove(a[curL++]);
    while (curR > r[i])
      remove(a[curR--]);
    ans[i] = calc(smallCnt, bigCnt, r[i] - l[i] + 1);
  }

  for (auto x : ans)
    cout << x << '\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