Submission #646445

#TimeUsernameProblemLanguageResultExecution timeMemory
646445sofijavelkovskaDiversity (CEOI21_diversity)C++14
64 / 100
7045 ms9164 KiB
#include <bits/stdc++.h> using namespace std; long long sqrtn; bool queriessort(tuple<long long, long long, long long> x, tuple<long long, long long, long long> y) { long long l1, r1, i1, l2, r2, i2; tie(l1, r1, i1)=x; tie(l2, r2, i2)=y; if (l1/sqrtn==l2/sqrtn) return r1<r2; return (l1/sqrtn<l2/sqrtn); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); long long n, q, i; cin >> n >> q; long long a[n]; tuple<long long, long long, long long> queries[q]; sqrtn=sqrt(n); for (i=0; i<n; i++) cin >> a[i]; for (i=0; i<q; i++) { long long l, r; cin >> l >> r; queries[i]={l-1, r-1, i}; } sort(queries, queries+q, queriessort); long long frequency[300001]={0}, compressed[n+1]={0}; long long x=0, y=0; set<long long> nonzero; frequency[a[0]]=1; compressed[1]=1; nonzero.insert(1); long long answer[q]; for (i=0; i<q; i++) { long long lt, rt, index; tie(lt, rt, index)=queries[i]; /*if (i!=0 && lt/sqrtn>get<0>(queries[i-1])/sqrtn) { x=lt-lt%sqrtn; y=lt-lt%sqrtn; for (int j=0; j<=300000; j++) frequency[j]=0; for (int j=0; j<=n; j++) compressed[j]=0; nonzero.clear(); frequency[a[x]]=1; compressed[1]=1; nonzero.insert(1); }*/ while (lt>x) { compressed[frequency[a[x]]]=compressed[frequency[a[x]]]-1; if (compressed[frequency[a[x]]]==0) nonzero.erase(frequency[a[x]]); frequency[a[x]]=frequency[a[x]]-1; compressed[frequency[a[x]]]=compressed[frequency[a[x]]]+1; if (compressed[frequency[a[x]]]==1) nonzero.insert(frequency[a[x]]); x=x+1; } while (lt<x) { x=x-1; compressed[frequency[a[x]]]=compressed[frequency[a[x]]]-1; if (compressed[frequency[a[x]]]==0) nonzero.erase(frequency[a[x]]); frequency[a[x]]=frequency[a[x]]+1; compressed[frequency[a[x]]]=compressed[frequency[a[x]]]+1; if (compressed[frequency[a[x]]]==1) nonzero.insert(frequency[a[x]]); } while (rt>y) { y=y+1; compressed[frequency[a[y]]]=compressed[frequency[a[y]]]-1; if (compressed[frequency[a[y]]]==0) nonzero.erase(frequency[a[y]]); frequency[a[y]]=frequency[a[y]]+1; compressed[frequency[a[y]]]=compressed[frequency[a[y]]]+1; if (compressed[frequency[a[y]]]==1) nonzero.insert(frequency[a[y]]); } while (rt<y) { compressed[frequency[a[y]]]=compressed[frequency[a[y]]]-1; if (compressed[frequency[a[x]]]==0) nonzero.erase(frequency[a[x]]); frequency[a[y]]=frequency[a[y]]-1; compressed[frequency[a[y]]]=compressed[frequency[a[y]]]+1; if (compressed[frequency[a[y]]]==1) nonzero.insert(frequency[a[y]]); y=y-1; } long long l=0; long long r=0; bool odd=false; long long nc=y-x+1; nonzero.erase(0); long long kc=0; for (auto xc : nonzero) kc=kc+compressed[xc]; long long s=kc*nc*(nc+1)-nc*(kc-1); for (auto xc : nonzero) { long long n1, n2; if (compressed[xc]%2==1) { if (odd) { n1=compressed[xc]/2; n2=(compressed[xc]+1)/2; odd=false; } else { n1=(compressed[xc]+1)/2; n2=compressed[xc]/2; odd=true; } } else { n1=compressed[xc]/2; n2=compressed[xc]/2; } s=s-(n1*l*l+xc*xc*((n1-1)*n1*(2*(n1-1)+1)/6)+2*xc*l*((n1-1)*n1/2)); s=s-(n1*(nc-l-xc)*(nc-l-xc)+xc*xc*((n1-1)*n1*(2*(n1-1)+1)/6)-2*xc*(nc-l-xc)*((n1-1)*n1/2)); s=s-(n2*r*r+xc*xc*((n2-1)*n2*(2*(n2-1)+1)/6)+2*xc*r*((n2-1)*n2/2)); s=s-(n2*(nc-r-xc)*(nc-r-xc)+xc*xc*((n2-1)*n2*(2*(n2-1)+1)/6)-2*xc*(nc-r-xc)*((n2-1)*n2/2)); l=l+n1*xc; r=r+n2*xc; } s=s/2; answer[index]=s; } for (i=0; i<q; i++) cout << answer[i] << '\n'; return 0; }
#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...