Submission #492973

#TimeUsernameProblemLanguageResultExecution timeMemory
492973blueDiversity (CEOI21_diversity)C++17
100 / 100
4353 ms11452 KiB
#include <iostream> #include <vector> #include <algorithm> #include <deque> using namespace std; const int mx = 300'000; const int mxQ = 50'000; const int rt = 500; using ll = long long; using vi = vector<int>; using vll = vector<ll>; #define sz(x) (int(x.size())) int N, Q; vi a(1+mx); vi l(1+mxQ), r(1+mxQ); vll ans(1+mxQ); int L = 1; int R = 0; vll ct(1+mx, 0); vll freq(1+mx, 0); vector<ll> sizes; vector<bool> occ(1+mx, 0); ll ap_sum(ll a, ll d, ll n) { return (n * (2*a + (n-1)*d))/2; } ll ap_sq_sum(ll a, ll d, ll n) { return n*a*a + a*d*(n-1)*n + d*d*(((n-1)*n*(2*n-1))/6); } ll get_ans() { vector<ll> sizes2; for(ll s: sizes) { if(occ[s]) continue; if(freq[s] == 0) continue; sizes2.push_back(s); occ[s] = 1; } sizes = sizes2; for(ll s: sizes) occ[s] = 0; sort(sizes.begin(), sizes.end(), [] (int u, int v) { return u > v; }); deque< pair<ll, ll> > ord; int z = 0; for(ll s: sizes) { if(freq[s] % 2 == 1) { // cerr << "odd!\n"; if(z) ord.push_back({s, 1}); else ord.push_front({s, 1}); z = !z; } if(freq[s]/2) { // cerr << "breaking into 2\n"; ord.push_back({s, freq[s]/2}); ord.push_front({s, freq[s]/2}); } } ord.push_front({0, 0}); ll ans = 0; ll tot = 0; int P = sz(ord) - 1; vll prefsum(1+P, 0); for(int i = 1; i <= P; i++) { prefsum[i] = prefsum[i-1] + (ord[i].first * ord[i].second); } tot = prefsum[P]; for(int i = 1; i <= P; i++) { ans += ord[i].second * (ord[i].first * (ord[i].first + 1))/2; ans += ord[i].second * (ord[i].first * (tot - ord[i].first)); ans += (tot - ord[i].first) * ap_sum(prefsum[i-1], ord[i].first, ord[i].second); ans -= ap_sq_sum(prefsum[i-1], ord[i].first, ord[i].second); } return ans; } void add_species(int a) { freq[ct[a]]--; ct[a]++; freq[ct[a]]++; sizes.push_back(ct[a]); } void remove_species(int a) { freq[ct[a]]--; ct[a]--; freq[ct[a]]++; sizes.push_back(ct[a]); } void expand_right() { R++; add_species(a[R]); } void expand_left() { L--; add_species(a[L]); } void contract_right() { remove_species(a[R]); R--; } void contract_left() { remove_species(a[L]); L++; } int main() { cin >> N >> Q; for(int i = 1; i <= N; i++) cin >> a[i]; for(int j = 1; j <= Q; j++) cin >> l[j] >> r[j]; vi I(Q); for(int j = 0; j < Q; j++) I[j] = j+1; sort(I.begin(), I.end(), [] (int u, int v) { if(l[u]/rt != l[v]/rt) return l[u]/rt < l[v]/rt; else return r[u] < r[v]; }); freq[0] = mx; for(int q: I) { while(R < r[q]) expand_right(); while(L > l[q]) expand_left(); while(R > r[q]) contract_right(); while(L < l[q]) contract_left(); ans[q] = get_ans(); } for(int q = 1; q <= Q; q++) cout << ans[q] << '\n'; }
#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...