Submission #531396

#TimeUsernameProblemLanguageResultExecution timeMemory
531396azberjibiouDiversity (CEOI21_diversity)C++17
100 / 100
6861 ms5972 KiB
#include <bits/stdc++.h> #define gibon ios::sync_with_stdio(false); cin.tie(0); #define fir first #define sec second #define pdd pair<double, double> #define pii pair<int, int> #define pll pair<ll, ll> #define pmax pair<__int128, __int128> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") typedef long long ll; using namespace std; int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0}; const int mxN=300003; const int mxM=1010; const int mxK=105; const int MOD=1000000007; const ll INF=1e18; const ll P1=1000000007; const ll P2=1000000009; typedef struct query{ int s, e, idx; ll ans; }query; int N, M, K, Q, L; int A[mxN]; query T[mxN]; int ncnt[mxN]; ///number int tcnt[mxN]; ///type int typ_cnt; int ns=1, ne; multiset <int> s; ll ans; ll lval, rval; int nsum; bool cmp1(query a, query b) { if(a.s/M!=b.s/M) return a.s<b.s; return a.e<b.e; } void set_remove(int now) { if(now<=K) tcnt[now]--; else s.erase(s.lower_bound(now)); } void set_insert(int now) { if(now<=K) tcnt[now]++; else s.insert(now); } void mo(int pos, int typ) { int pre=ncnt[A[pos]], now=ncnt[A[pos]]+typ; ncnt[A[pos]]+=typ; if(pre==0) typ_cnt++; if(now==0) typ_cnt--; set_remove(pre); set_insert(now); } ll sum(ll a, ll d, ll n) { return (a*(a+1)*n+(2*a+1)*d*n*(n-1)/2+d*d*(n-1)*n*(2*n-1)/6)/2; } void typ_insert(int now, int num) { if(num==0) return; nsum+=num; if(nsum==typ_cnt) num--; if(num==0) return; if(lval>rval) swap(lval, rval); int lcnt=0, rcnt=0; lcnt+=min((ll)num, (rval-lval)/now); num-=lcnt; if(num%2==0) lcnt+=num/2, rcnt+=num/2; else lcnt+=num/2+1, rcnt+=num/2; ans-=sum(lval+now, now, lcnt); ans-=sum(L-lval-lcnt*now, now, lcnt); lval+=lcnt*now; ans-=sum(rval+now, now, rcnt); ans-=sum(L-rval-rcnt*now, now, rcnt); rval+=rcnt*now; } void print() { for(int i=1;i<=M;i++) printf("cnt[%d]=%d\n", i, tcnt[i]); for(auto iter=s.begin();iter!=s.end();iter++) printf("%d ", *iter); printf("\n"); } int main() { gibon cin >> N >> Q; M=sqrt(Q); K=min(N, (int)(2*sqrt(N)*log2(N))); for(int i=1;i<=N;i++) cin >> A[i]; for(int i=0;i<Q;i++) { cin >> T[i].s >> T[i].e; T[i].idx=i; } sort(T, T+Q, cmp1); for(int i=0;i<Q;i++) { while(ne<T[i].e) { ne++; mo(ne, 1); } while(ns>T[i].s) { ns--; mo(ns, 1); } while(ne>T[i].e) { mo(ne, -1); ne--; } while(ns<T[i].s) { mo(ns, -1); ns++; } L=T[i].e-T[i].s+1; nsum=0; ans=(ll)L*(L+1)/2*typ_cnt; lval=0, rval=0; for(int i=1;i<=K;i++) { typ_insert(i, tcnt[i]); } for(auto iter=s.begin();iter!=s.end();iter++) { typ_insert(*iter, 1); } T[i].ans=ans; } sort(T, T+Q, [](query a, query b){return a.idx<b.idx;}); for(int i=0;i<Q;i++) cout << T[i].ans << '\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...