Submission #832095

#TimeUsernameProblemLanguageResultExecution timeMemory
832095QwertyPiDiversity (CEOI21_diversity)C++14
100 / 100
5907 ms8076 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define int long long using namespace std; const int MAXN = 3e5 + 11; const int MAXQ = 5e4 + 11; const int SQ = 1000; int a[MAXN]; int ans[MAXQ]; int c[MAXN], cc[MAXN]; int s0, s1, s2; set<int> s; void add(int x){ s0 -= c[x] * (c[x] + 1) / 2; s1 -= c[x]; s2 -= c[x] * c[x]; cc[c[x]]--; if(cc[c[x]] == 0) s.erase(c[x]); c[x]++; s0 += c[x] * (c[x] + 1) / 2; s1 += c[x]; s2 += c[x] * c[x]; cc[c[x]]++; if(cc[c[x]] == 1) s.insert(c[x]); } void rem(int x){ s0 -= c[x] * (c[x] + 1) / 2; s1 -= c[x]; s2 -= c[x] * c[x]; cc[c[x]]--; if(cc[c[x]] == 0) s.erase(c[x]); c[x]--; s0 += c[x] * (c[x] + 1) / 2; s1 += c[x]; s2 += c[x] * c[x]; cc[c[x]]++; if(cc[c[x]] == 1) s.insert(c[x]); } int f(int x0, int d, int y, int n){ int t1 = n * d * (x0 * 2 + (d - 1) * y) / 2; int t2 = d * x0 * x0; int t3 = (d - 1) * d * x0 * y; int t4 = (d - 1) * d * (d * 2 - 1) / 6 * y * y; return t1 - t2 - t3 - t4; } struct query{ int l, r, id; }; int32_t main(){ int n, q; cin >> n >> q; for(int i = 0; i < n; i++){ cin >> a[i]; } vector<query> Q; for(int i = 0; i < q; i++){ int l, r; cin >> l >> r; --l; --r; Q.push_back({l, r, i}); } sort(Q.begin(), Q.end(), [](query a, query b){ if(a.l / SQ != b.l / SQ) return a.l / SQ < b.l / SQ; return a.l / SQ % 2 ? a.r > b.r : a.r < b.r; }); int l = 0, r = -1; for(auto [ql, qr, id] : Q){ while(l > ql) add(a[--l]); while(r < qr) add(a[++r]); while(l < ql) rem(a[l++]); while(r > qr) rem(a[r--]); int res = s0 + (s1 * s1 - s2) / 2; int cl = 0, cr = 0; for(auto y : s){ if(cl > cr) swap(cl, cr); int cnt = cc[y]; int d = min(cnt, (cr - cl) / y); res += f(cl, d, y, s1); cl += d * y; cnt -= d; res += f(cl, (cnt + 1) / 2, y, s1); res += f(cr, cnt / 2, y, s1); cl += ((cnt + 1) / 2) * y, cr += (cnt / 2) * y; } res += cl * (s1 - cl); ans[id] = res; } for(int i = 0; i < q; i++){ cout << ans[i] << '\n'; } }

Compilation message (stderr)

diversity.cpp: In function 'int32_t main()':
diversity.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [ql, qr, id] : Q){
      |              ^
#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...