This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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){
return n * d * (x0 * 2 + (d - 1) * y) / 2 - d * x0 * x0 - (d - 1) * d * x0 * y - (d - 1) * d * (d * 2 - 1) * y * y;
}
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:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for(auto [ql, qr, id] : Q){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |