Submission #993841

#TimeUsernameProblemLanguageResultExecution timeMemory
993841vladiliusDiversity (CEOI21_diversity)C++17
0 / 100
3 ms3932 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); set<pii> st; vector<int> cnt(A + 1); int l = n, r = n - 1; bool ind; auto pp = [&](int x){ if (x % 2 == 0){ return l + x / 2 - 1; } return r - x / 2; }; ll sum = 0; auto add = [&](int i){ if (!i) return; int k = cnt[a[i]]; sum += (k + 1); if (st.empty()){ ind = 1; } else { int f = (*prev(st.end())).ss; ind = (f < (1.0 * (l + r) / 2)); } int p; if (!k){ p = ((ind) ? (l - 1) : (r + 1)); } else { p = pp((int) T.get(k)); } 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.erase({k, p}); } cnt[a[i]]++; k++; T.upd(k, 1); st.ins({k, p}); // 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...