Submission #993857

#TimeUsernameProblemLanguageResultExecution timeMemory
993857vladiliusDiversity (CEOI21_diversity)C++17
4 / 100
10 ms18012 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define ins insert #define arr3 array<int, 3> const int A = 3e5; struct FT{ vector<ll> bit; int n; FT(int ns){ n = ns; bit.resize(n + 1); } void upd(int p, int k){ // a[p] += k while (p <= n){ bit[p] += k; p |= (p + 1); } } ll get(int v){ // a[1] + ... + a[v] ll out = 0; while (v > 0){ out += bit[v]; v = (v & (v + 1)) - 1; } return out; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin>>n>>q; vector<int> a(n + 1); for (int i = 1; i <= n; i++){ cin>>a[i]; } if (q > 1) return 0; vector<arr3> all; for (int i = 1; i <= q; i++){ int l, r; cin>>l>>r; all.pb({l, r, i}); } const int sz = sqrt(n); auto cmp = [&](arr3& x, arr3& y){ if (x[0] / sz == x[1] / sz){ return x[1] < y[1]; } return x[0] < y[0]; }; sort(all.begin(), all.end(), cmp); int nn = 2 * n; FT T(A), Ts(nn), Tp(nn), T1(nn); set<double> st[A + 1]; vector<int> cnt(A + 1); int l = n, r = n - 1; bool ind; ll sum = 0; auto add = [&](int i){ if (!i) return; int k = cnt[a[i]]; sum += (k + 1); int p; if (!k){ ll s1 = 0; p = l - 1; s1 += (1LL * (p + 1) * Ts.get(p - 1) - Tp.get(p - 1)); s1 += ((Tp.get(nn) - Tp.get(p)) - 1LL * (p - 1) * (Ts.get(nn) - Ts.get(p))); ll s2 = 0; p = r + 1; s2 += (1LL * (p + 1) * Ts.get(p - 1) - Tp.get(p - 1)); s2 += ((Tp.get(nn) - Tp.get(p)) - 1LL * (p - 1) * (Ts.get(nn) - Ts.get(p))); if (s1 < s2){ p = l - 1; ind = 1; } else { ind = 0; } } else { double m = (l + r) / 2.0; auto it = st[k].lower_bound(m); if (it == st[k].end()){ p = *prev(it); } else if (it == st[k].begin()){ p = *it; } else { auto it1 = prev(it); if (abs((double) *it1 - m) < abs((double) *it - m)){ p = *it1; } else { p = *it; } } } sum += (1LL * (p + 1) * Ts.get(p - 1) - Tp.get(p - 1)); sum += ((Tp.get(nn) - Tp.get(p)) - 1LL * (p - 1) * (Ts.get(nn) - Ts.get(p))); Ts.upd(p, 1); Tp.upd(p, p); if (!k){ if (ind) l--; else r++; } else { T.upd(k, -1); st[k].erase(p); if (k == 1) T1.upd(p, -1); } cnt[a[i]]++; k++; T.upd(k, 1); st[k].ins(p); if (k == 1) T1.upd(p, 1); // cout<<"Yo "<<l<<" "<<r<<" "<<p<<"\n"; }; auto rem = [&](int i){ }; vector<ll> out(q + 1); int lc = 0, rc = 0; for (int i = 0; i < q; i++){ auto &[l, r, ii] = all[i]; while (lc > l) add(--lc); while (rc < r) add(++rc); while (lc < l) rem(lc++); while (rc > r) rem(rc--); out[ii] = sum; } for (int i = 1; i <= q; i++){ cout<<out[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...