oj.uz

Submission #1052886

# Submission time Handle Problem Language Result Execution time Memory
1052886 2024-08-11T05:30:47 Z kunzaZa183 Diversity (CEOI21_diversity) C++17
4 / 100
 12 ms 25032 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};
  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

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 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24924 KB Output is correct
4 Correct 10 ms 24924 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 12 ms 25008 KB Output is correct
7 Correct 10 ms 24924 KB Output is correct
8 Correct 10 ms 25000 KB Output is correct
9 Correct 12 ms 24928 KB Output is correct
10 Correct 11 ms 24920 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 12 ms 24924 KB Output is correct
3 Incorrect 12 ms 25032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 12 ms 24924 KB Output is correct
3 Incorrect 12 ms 25032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 12 ms 24924 KB Output is correct
3 Incorrect 12 ms 25032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24924 KB Output is correct
4 Correct 10 ms 24924 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 12 ms 25008 KB Output is correct
7 Correct 10 ms 24924 KB Output is correct
8 Correct 10 ms 25000 KB Output is correct
9 Correct 12 ms 24928 KB Output is correct
10 Correct 11 ms 24920 KB Output is correct
11 Correct 10 ms 24924 KB Output is correct
12 Correct 12 ms 24924 KB Output is correct
13 Incorrect 12 ms 25032 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24924 KB Output is correct
4 Correct 10 ms 24924 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 12 ms 25008 KB Output is correct
7 Correct 10 ms 24924 KB Output is correct
8 Correct 10 ms 25000 KB Output is correct
9 Correct 12 ms 24928 KB Output is correct
10 Correct 11 ms 24920 KB Output is correct
11 Correct 10 ms 24924 KB Output is correct
12 Correct 12 ms 24924 KB Output is correct
13 Incorrect 12 ms 25032 KB Output isn't correct
14 Halted 0 ms 0 KB -