제출 #1052865

#제출 시각아이디문제언어결과실행 시간메모리
1052865kunzaZa183Diversity (CEOI21_diversity)C++17
4 / 100
4 ms1628 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 = 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"; }

컴파일 시 표준 에러 (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));
      |               ~~~~~~~~~~~~~~~~~~^~~~
#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...