Submission #1052864

#TimeUsernameProblemLanguageResultExecution timeMemory
1052864kunzaZa183Diversity (CEOI21_diversity)C++17
0 / 100
44 ms348 KiB
#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 = 8, 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:23: warning: unused variable 'maxk' [-Wunused-variable]
    9 |   const int maxn = 8, 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));
      |               ~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...