Submission #956777

#TimeUsernameProblemLanguageResultExecution timeMemory
956777TAhmed33Diversity (CEOI21_diversity)C++98
100 / 100
1799 ms14072 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") typedef long long ll; const int MAXN = 3e5 + 1; const int B = 700; int a[MAXN], n, q; array <int, 3> queries[MAXN]; ll ans[MAXN]; int freq[MAXN], freq2[2 * MAXN + 1]; vector <int> large; void add (int x) { freq2[freq[a[x]] + MAXN]--; freq[a[x]]++; freq2[freq[a[x]] + MAXN]++; } void rem (int x) { freq2[freq[a[x]] + MAXN]--; freq[a[x]]--; freq2[freq[a[x]] + MAXN]++; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q; freq2[MAXN] = MAXN; for (int i = 1; i <= n; i++) cin >> a[i], freq[a[i]]++; for (int i = 1; i < MAXN; i++) { if (freq[i] > B) { large.push_back(i); } } memset(freq, 0, sizeof(freq)); for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; queries[i] = {l, r, i}; } sort(queries + 1, queries + q + 1, [&] (array <int, 3> &x, array <int, 3> &y) { return x[0] / B == y[0] / B ? x[1] < y[1] : x[0] / B < y[0] / B; }); int L = queries[1][0] + 1, R = queries[1][0]; for (int i = 1; i <= q; i++) { while (L > queries[i][0]) add(--L); while (L < queries[i][0]) rem(L++); while (R > queries[i][1]) rem(R--); while (R < queries[i][1]) add(++R); ll dis = 0; ll n = R - L + 1; vector <pair <ll, ll>> pp[2]; int c = 0; for (int j = 1; j <= B; j++) { dis += freq2[j + MAXN]; int x = j, y = freq2[j + MAXN]; if (y == 1) { pp[c].push_back({x, 1}); c ^= 1; } else { int l = (y + 1) / 2, r = y / 2; pp[c].push_back({x, l}); pp[c ^ 1].push_back({x, r}); c ^= (y & 1); } } sort(large.begin(), large.end(), [&] (int x, int y) { return freq[x] < freq[y]; }); for (auto j : large) { if (!freq[j] || freq[j] <= B) continue; dis++; int x = freq[j], y = 1; if (y == 1) { pp[c].push_back({x, 1}); c ^= 1; } else { int l = (y + 1) / 2, r = y / 2; pp[c].push_back({x, l}); pp[c ^ 1].push_back({x, r}); c ^= (y & 1); } } reverse(pp[1].begin(), pp[1].end()); ll cur = 0, pref = 0; for (auto [x, y] : pp[0]) { cur += pref * pref * y + y * (y - 1) / 2 * 2 * pref * x + x * x * (y - 1) * y * (2 * y - 1) / 6 + y * pref + x * y * (y - 1) / 2; cur += y * n * n - y * n * pref - n * y * (y + 1) / 2 * x + y * n; cur += -y * n * pref + pref * pref * y + pref * y * (y + 1) / 2 * x - y * pref; cur += -n * y * (y + 1) / 2 * x + y * (y + 1) / 2 * x * pref + x * x * y * (y + 1) * (2 * y + 1) / 6 - y * (y + 1) / 2 * x; pref += x * y; } for (auto [x, y] : pp[1]) { cur += pref * pref * y + y * (y - 1) / 2 * 2 * pref * x + x * x * (y - 1) * y * (2 * y - 1) / 6 + y * pref + x * y * (y - 1) / 2; cur += y * n * n - y * n * pref - n * y * (y + 1) / 2 * x + y * n; cur += -y * n * pref + pref * pref * y + pref * y * (y + 1) / 2 * x - y * pref; cur += -n * y * (y + 1) / 2 * x + y * (y + 1) / 2 * x * pref + x * x * y * (y + 1) * (2 * y + 1) / 6 - y * (y + 1) / 2 * x; pref += x * y; } ans[queries[i][2]] = n * (n + 1) / 2 * dis - cur / 2; } for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:82:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |   for (auto [x, y] : pp[0]) {
      |             ^
diversity.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [x, y] : pp[1]) {
      |             ^
#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...