제출 #1233872

#제출 시각아이디문제언어결과실행 시간메모리
1233872MatthewwwwDiversity (CEOI21_diversity)C++17
64 / 100
7091 ms69720 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #ifdef LOCAL #define err cerr #else #define err if (0) cerr #endif const int sq = 821; struct Sgt { ll l, r, v, t, e; int tl, tr; Sgt *lft, *rht; Sgt (int l, int r): l(0), r(0), v(0), t(0), e(1), tl(l), tr(r) { if (tl != tr-1) { int tm = tl+tr>>1; lft = new Sgt(tl, tm); rht = new Sgt(tm, tr); } } void update (int i, int x) { if (tl == tr-1) { ll d = t+x; l = r = t = d; v = d*(d+1)/2; return; } (i < lft->tr ? lft : rht)->update(i, x); l = lft->l+rht->l+lft->e*rht->t; r = lft->r+rht->r+lft->t*rht->e; v = lft->v+rht->v+lft->t*rht->l+lft->r*rht->t; t = lft->t+rht->t; e = lft->e+rht->e; } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> vt(n); for (int &i: vt) cin >> i; vector<int> cc(vt.begin(), vt.end()); sort(cc.begin(), cc.end()); cc.erase(unique(cc.begin(), cc.end()), cc.end()); for (int &i: vt) i = lower_bound(cc.begin(), cc.end(), i)-cc.begin(); int m = cc.size()+cc.size()%2; vector<int> cnt(m, 0); vector<int> tag(m); iota(tag.begin(), tag.end(), 0); Sgt *sgt[2]; sgt[0] = new Sgt(0, m/2); sgt[1] = new Sgt(0, m/2); vector<map<int, int>> st(n+9); for (int i = 0; i < m; i++) st[0][tag[i]] = i; vector<pair<int, int>> qs(q); for (auto &i: qs) { cin >> i.f >> i.s; i.f--; } vector<vector<int>> bucket(n/sq+1); for (int i = 0; i < q; i++) bucket[qs[i].f/sq].push_back(i); for (auto &i: bucket) sort(i.begin(), i.end(), [&](int a, int b) { return qs[a].s < qs[b].s;}); vector<int> ord; vector<ll> ans(q); for (auto i: bucket) for (int j: i) ord.push_back(j); int l = 0, r = 0; auto rmv = [&](int i) { if (st[cnt[i]].size()) { int h = (*st[cnt[i]].begin()).s; if (h != i) { st[cnt[i]].erase(tag[h]); st[cnt[i]][tag[i]] = h; swap(tag[h], tag[i]); cnt[i]--; st[cnt[i]][tag[i]] = i; } else { st[cnt[i]].erase(tag[i]); cnt[i]--; st[cnt[i]][tag[i]] = i; } } else { st[cnt[i]].erase(tag[i]); cnt[i]--; st[cnt[i]][tag[i]] = i; } sgt[tag[i]%2]->update(tag[i]/2, -1); }; auto add = [&](int i) { if (st[cnt[i]].size()) { int h = (*--st[cnt[i]].end()).s; if (h != i) { st[cnt[i]].erase(tag[h]); st[cnt[i]][tag[i]] = h; swap(tag[h], tag[i]); cnt[i]++; st[cnt[i]][tag[i]] = i; } else { st[cnt[i]].erase(tag[i]); cnt[i]++; st[cnt[i]][tag[i]] = i; } } else { st[cnt[i]].erase(tag[i]); cnt[i]++; st[cnt[i]][tag[i]] = i; } sgt[tag[i]%2]->update(tag[i]/2, 1); }; for (int i: ord) { auto p = qs[i]; while (r < p.s) add(vt[r++]); while (l > p.f) add(vt[--l]); while (l < p.f) rmv(vt[l++]); while (r > p.s) rmv(vt[--r]); ans[i] = sgt[0]->v+sgt[1]->v+sgt[0]->t*sgt[1]->r+sgt[1]->t*sgt[0]->r; } for (ll i: ans) cout << i << "\n"; } // no llama :( // i miss you
#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...