Submission #1052887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052887		kunzaZa183	Diversity (CEOI21_diversity)	C++17	64 / 100	7063 ms	25180 KiB

diversity

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

  const int maxn = 300005, maxq = 50000;
  
  block = sqrt(n) + 3;

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

  struct query {
    pair<int, int> pii;
    int in;
    bool operator<(query x) const {
      if (pii.first / block != x.pii.first / block) return pii < x.pii;
      return pii.second > x.pii.second;
    }
  };
  query arrpii[maxn];
  for (int i = 0; i < q; i++) {
    cin >> arrpii[i].pii.first >> arrpii[i].pii.second;
    arrpii[i].pii.first--, arrpii[i].pii.second--;
    arrpii[i].in = i;
  }

  sort(arrpii, arrpii + n);

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

    long long sum(int r) {
      long long 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] = {};

  long long curans = 0;
  auto add = [&](int in) {
    int tmp = status[at[arr[in]]].second - 1;
    curans -= (long long)(at[arr[in]] + 1) * at[arr[in]] / 2;
    curans += (long long)(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--;
  };

  auto rem = [&](int in) {
    int tmp = status[at[arr[in]]].first;
    curans -= (long long)(at[arr[in]] + 1) * at[arr[in]] / 2;
    curans += (long long)(at[arr[in]]) * (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]]].first++;
    at[arr[in]]--;

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

  pair<int, int> last = {0, -1};
  long long ans[maxn];
  for (int i = 0; i < q; i++) {
    while (arrpii[i].pii.second > last.second) {
      last.second++;
      add(last.second);
    }

    while (arrpii[i].pii.first < last.first) {
      last.first--;
      add(last.first);
    }

    while (arrpii[i].pii.second < last.second) {
      rem(last.second);
      last.second--;
    }

    while (arrpii[i].pii.first > last.first) {
      rem(last.first);
      last.first++;
    }
    ans[arrpii[i].in] = curans;
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:10:28: warning: unused variable 'maxq' [-Wunused-variable]
   10 |   const int maxn = 300005, maxq = 50000;
      |                            ^~~~
diversity.cpp: In lambda function:
diversity.cpp:76:33: warning: 'coord' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |               (2 * maxn - coord - 1) * (normal.sum(coord - 1) - normal.sum(0));
      |               ~~~~~~~~~~~~~~~~~~^~~~
diversity.cpp: In lambda function:
diversity.cpp:103:33: warning: 'coord' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |               (2 * maxn - coord - 1) * (normal.sum(coord - 1) - normal.sum(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