Submission #1084175

#TimeUsernameProblemLanguageResultExecution timeMemory
1084175onlk97Diversity (CEOI21_diversity)C++14
64 / 100
7062 ms5476 KiB
#include <bits/stdc++.h> using namespace std; int L,R; int a[300010]; long long freq[300010],freq2[300010]; bitset <300010> have; long long calcans(){ long long ans=0,lps=0,rps=0,s=R-L+1; for (int i=have._Find_first(); i<300010; i=have._Find_next(i)){ long long cntl,cntr; int f; if (lps<=rps){ f=min(freq2[i],(rps-lps)/i+1); cntl=f+(freq2[i]-f)/2,cntr=(freq2[i]-f+1)/2; } else { f=min(freq2[i],(lps-rps)/i+1); cntl=(freq2[i]-f+1)/2,cntr=f+(freq2[i]-f)/2; } ans+=cntl*lps*lps+cntl*(cntl+1)*lps*i+cntl*(cntl+1)/2*(2*cntl+1)/3*i*i; ans-=s*(lps+i+lps+i*cntl)*cntl/2; lps+=cntl*i; long long t=s-rps; ans+=cntr*t*t-cntr*(cntr-1)*t*i+(cntr)*(cntr-1)/2*(2*cntr-1)/3*i*i; ans-=s*(t+t-(cntr-1)*i)*cntr/2; rps+=cntr*i; } return s*(s+1)/2-ans; } const int BLOCK=600; bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){ int ax=a.first.first/BLOCK,bx=b.first.first/BLOCK; if (ax!=bx) return ax<bx; return a.first.second<b.first.second; } int main(){ int n,q; cin>>n>>q; for (int i=1; i<=n; i++) cin>>a[i]; pair <pair <int,int>,int> qu[q+1]; for (int i=1; i<=q; i++){ cin>>qu[i].first.first>>qu[i].first.second; qu[i].second=i; } sort(qu+1,qu+q+1,cmp); L=1; R=0; long long op[q+1]; for (int i=1; i<=q; i++){ while (R<qu[i].first.second){ R++; if (freq[a[R]]) freq2[freq[a[R]]]--; freq[a[R]]++; if (!freq2[freq[a[R]]]) have[freq[a[R]]]=1; freq2[freq[a[R]]]++; } while (L>qu[i].first.first){ L--; if (freq[a[L]]) freq2[freq[a[L]]]--; freq[a[L]]++; if (!freq2[freq[a[L]]]) have[freq[a[L]]]=1; freq2[freq[a[L]]]++; } while (R>qu[i].first.second){ freq2[freq[a[R]]]--; freq[a[R]]--; if (freq[a[R]]&&!freq2[freq[a[R]]]) have[freq[a[R]]]=1; freq2[freq[a[R]]]++; R--; } while (L<qu[i].first.first){ freq2[freq[a[L]]]--; freq[a[L]]--; if (freq[a[L]]&&!freq2[freq[a[L]]]) have[freq[a[L]]]=1; freq2[freq[a[L]]]++; L++; } op[qu[i].second]=calcans(); } for (int i=1; i<=q; i++) cout<<op[i]<<'\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...