Submission #956757

#TimeUsernameProblemLanguageResultExecution timeMemory
956757TAhmed33Diversity (CEOI21_diversity)C++98
64 / 100
7056 ms9808 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") typedef long long ll; const int MAXN = 3e5 + 1; const int B = 1000; int a[MAXN], n, q; array <int, 3> queries[MAXN]; ll ans[MAXN]; int freq[MAXN], freq2[2 * MAXN + 1]; set <int> t; void add (int x) { if (freq2[freq[a[x]] + MAXN] == 1) t.erase(freq[a[x]]); freq2[freq[a[x]] + MAXN]--; freq[a[x]]++; freq2[freq[a[x]] + MAXN]++; if (freq2[freq[a[x]] + MAXN] == 1) t.insert(freq[a[x]]); } void rem (int x) { if (freq2[freq[a[x]] + MAXN] == 1) t.erase(freq[a[x]]); freq2[freq[a[x]] + MAXN]--; freq[a[x]]--; freq2[freq[a[x]] + MAXN]++; if (freq2[freq[a[x]] + MAXN] == 1) t.insert(freq[a[x]]); } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q; freq2[MAXN] = MAXN; t.insert(0); for (int i = 1; i <= n; i++) cin >> a[i]; 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 (auto j : t) { if (!j) continue; 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); } } 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:63:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |   for (auto [x, y] : pp[0]) {
      |             ^
diversity.cpp:70:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |   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...