Submission #1052865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052865		kunzaZa183	Diversity (CEOI21_diversity)	C++17	4 / 100	4 ms	1628 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0)->ios::sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  int n, q;
  cin >> n >> q;

  const int maxn = 10000, maxk = 1000;

  int block = sqrt(n) + 3;

  int arr[maxn];
  for (int i = 0; i < n; i++) cin >> arr[i];

  pair<int, int> pii[maxn];
  for (int i = 0; i < q; i++) {
    cin >> pii[i].first >> pii[i].second;
  }

  sort(pii, pii + n, [&](pair<int, int> a, pair<int, int> b) {
    if (a.first / block != b.first / block) return a.first < b.first;
    return a.second > b.second;
  });

  struct fenwick {
    int arr[2 * maxn + 1] = {};

    int sum(int r) {
      int ret = 0;
      for (r++; r > 0; r -= r & (-r)) ret += arr[r];
      return ret;
    }

    void add(int in, int val) {
      for (in++; in <= 2 * maxn; in += in & (-in)) {
        arr[in] += val;
      }
    }
  } ok, rev, normal;

  pair<int, int> status[maxn + 1];  // bef, cur
  status[0] = {0, n};
  for (int i = 1; i <= maxn; i++) status[i] = {n, n};

  int at[maxn] = {};

  int curans = 0;
  auto add = [&](int in) {
    int tmp = status[at[arr[in]]].second - 1;
    curans -= (at[arr[in]] + 1) * at[arr[in]] / 2;
    curans += (at[arr[in]] + 2) * (at[arr[in]] + 1) / 2;

    int coord;
    if (tmp % 2 == 1) {
      coord = maxn + 1 + (n - tmp  - 1) / 2;
    } else if (tmp % 2 == 0) {
      coord = maxn - (n - tmp - 1) / 2;
    }

    normal.add(coord, 1);
    ok.add(coord, coord);
    rev.add(coord, 2 * maxn - coord);

    curans += ok.sum(2 * maxn - 1) - ok.sum(coord) -
              (coord - 1) * (normal.sum(2 * maxn - 1) - normal.sum(coord));
    curans += rev.sum(coord - 1) - rev.sum(0) -
              (2 * maxn - coord - 1) * (normal.sum(coord - 1) - normal.sum(0));

    status[at[arr[in]]].second--;
    at[arr[in]]++;

    status[at[arr[in]]].first--;
  };

  for (int i = 0; i < n; i++) {
    add(i);
  }

  cout << curans << "\n";
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:9:27: warning: unused variable 'maxk' [-Wunused-variable]
    9 |   const int maxn = 10000, maxk = 1000;
      |                           ^~~~
diversity.cpp:68:33: warning: 'coord' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |               (2 * maxn - coord - 1) * (normal.sum(coord - 1) - normal.sum(0));
      |               ~~~~~~~~~~~~~~~~~~^~~~

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