Submission #859650

#TimeUsernameProblemLanguageResultExecution timeMemory
859650Tenis0206Diversity (CEOI21_diversity)C++11
4 / 100
231 ms460160 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int nmax = 3e5; const int c = 800; const int bsize = 550; struct qry { int st, dr, poz; }; int n,q; int v[nmax + 5]; int fr[nmax + 5]; int nrfr[nmax + 5]; int st[nmax + 5], dr[nmax + 5]; vector<int> l, h; int sp[c + 5][nmax + 5]; vector<qry> B[bsize + 5]; int sum_prod(int p, int st, int dr) { if(st - p <= 0) { return sp[p][dr]; } return sp[p][dr] - sp[p][st - p]; } int solve_heavy(int x, int y) { deque<int> d; for(int i=0; i<h.size(); i++) { if(i % 2 == 0) { d.push_back(h[i]); } else { d.push_front(h[i]); } } int sum_st = 0, sum_dr = 0; for(int i=1; i<=c; i++) { sum_st += st[i] * i; sum_dr += dr[i] * i; } for(auto it : d) { sum_dr += it; } int rez = 0; for(auto it : d) { sum_dr -= it; rez += 1LL * (y - x + 1) * (y - x + 2) / 2; rez -= 1LL * sum_st * (sum_st + 1) / 2; rez -= 1LL * sum_dr * (sum_dr + 1) / 2; sum_st += it; } return rez; } int solve_light(int x, int y) { int rez = 0; int sum_dr = 0, sum_st = 0; for(int i=1; i<=c; i++) { sum_dr += dr[i] * i; sum_dr += st[i] * i; } for(auto it : h) { sum_dr += it; } for(int i=1; i<=c; i++) { int cnt = st[i]; rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt; rez -= sum_prod(i, sum_st, sum_st + i * (cnt - 1)); rez -= sum_prod(i, sum_dr - i * cnt, sum_dr - i); sum_st += st[i] * i; sum_dr -= st[i] * i; } sum_dr = 0, sum_st = 0; for(int i=1; i<=c; i++) { sum_st += st[i] * i; sum_st += dr[i] * i; } for(auto it : h) { sum_st += it; } for(int i=1; i<=c; i++) { int cnt = dr[i]; rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt; rez -= sum_prod(i, sum_st - i * cnt, sum_st - i); rez -= sum_prod(i, sum_dr, sum_dr + i * (cnt - 1)); sum_st -= dr[i] * i; sum_dr += dr[i] * i; } return rez; } int query(int x, int y) { int nr = h.size(); for(int i=1; i<=c; i++) { if(nrfr[i]==0) { st[i] = dr[i] = 0; continue; } if(nrfr[i] % 2 == 0) { st[i] = dr[i] = nrfr[i] / 2; } else { if(nr % 2 == 0) { st[i] = nrfr[i] / 2; dr[i] = nrfr[i] / 2 + 1; } else { st[i] = nrfr[i] / 2 + 1; dr[i] = nrfr[i] / 2; } } nr += nrfr[i]; } int rez = 0; rez += solve_heavy(x,y); rez += solve_light(x,y); return rez; } void Add(int val) { --nrfr[fr[val]]; ++fr[val]; ++nrfr[fr[val]]; if(fr[val] > c) { l.push_back(val); } } void Remove(int val) { --nrfr[fr[val]]; --fr[val]; ++nrfr[fr[val]]; } void build_h() { vector<int> aux; h.clear(); for(auto it : l) { if(fr[it] > c) { aux.push_back(it); h.push_back(fr[it]); } } l = aux; sort(h.begin(),h.end(),greater<int>()); } void precalc() { for(int p=1; p<=c; p++) { for(int i=1; i<=n; i++) { sp[p][i] = 1LL * i * (i + 1) / 2; if(i - p > 0) { sp[p][i] += sp[p][i - p]; } } } } int get_bucket(int poz) { return (poz - 1) / bsize + 1; } bool cmp(qry a, qry b) { return (a.dr < b.dr); } int rez[nmax + 5]; signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef home freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); #endif // home cin>>n>>q; for(int i=1; i<=n; i++) { cin>>v[i]; } precalc(); for(int i=1; i<=q; i++) { qry x; cin>>x.st>>x.dr; x.poz = i; int bucket = get_bucket(x.st); B[bucket].push_back(x); } for(int b=1;b<=bsize+1;b++) { if(!B[b].size()) { continue; } sort(B[b].begin(), B[b].end(),cmp); int last_st = B[b].front().st, last_dr = B[b].front().st - 1; for(auto it : B[b]) { int st = it.st; int dr = it.dr; int poz = it.poz; for(int i=last_dr+1;i<=dr;i++) { Add(v[i]); } if(last_st < st) { for(int i=last_st;i<st;i++) { Remove(v[i]); } } else { for(int i=st;i<last_st;i++) { Add(v[i]); } } build_h(); rez[poz] = query(st,dr); last_st = st, last_dr = dr; } l.clear(); for(int i=1;i<=nmax;i++) { nrfr[i] = 0; fr[i] = 0; } } for(int i=1;i<=q;i++) { cout<<rez[i]<<'\n'; } return 0; }

Compilation message (stderr)

diversity.cpp: In function 'long long int solve_heavy(long long int, long long int)':
diversity.cpp:42:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0; i<h.size(); i++)
      |                  ~^~~~~~~~~
#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...