oj.uz

Submission #1052885

# Submission time Handle Problem Language Result Execution time Memory
1052885 2024-08-11T05:30:29 Z kunzaZa183 Diversity (CEOI21_diversity) C++17
4 / 100
 24 ms 23920 KB 
#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) {
      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] = {};

  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};
  int 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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 9 ms 23920 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 11 ms 23736 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 13 ms 23896 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23788 KB Output is correct
3 Correct 11 ms 23824 KB Output is correct
4 Incorrect 24 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23788 KB Output is correct
3 Correct 11 ms 23824 KB Output is correct
4 Incorrect 24 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23788 KB Output is correct
3 Correct 11 ms 23824 KB Output is correct
4 Incorrect 24 ms 23896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 9 ms 23920 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 11 ms 23736 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 13 ms 23896 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 10 ms 23788 KB Output is correct
13 Correct 11 ms 23824 KB Output is correct
14 Incorrect 24 ms 23896 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 9 ms 23920 KB Output is correct
3 Correct 9 ms 23900 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 11 ms 23736 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 13 ms 23896 KB Output is correct
11 Correct 11 ms 23900 KB Output is correct
12 Correct 10 ms 23788 KB Output is correct
13 Correct 11 ms 23824 KB Output is correct
14 Incorrect 24 ms 23896 KB Output isn't correct
15 Halted 0 ms 0 KB -