Submission #971714

#TimeUsernameProblemLanguageResultExecution timeMemory
971714SzilDiversity (CEOI21_diversity)C++14
100 / 100
6750 ms14944 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 300'001; const int BLOCK = 650; struct Query { int l, r, idx; bool operator<(Query x) const { if (l / BLOCK == x.l / BLOCK) return (l / BLOCK) & 1 ? r > x.r : r < x.r; return l < x.l; } }; int a[MAXN], b[MAXN], c[BLOCK]; map<int, int> act; ll ans[MAXN], negyzet[MAXN]; void inc(int v) { if (b[v] < BLOCK) { c[b[v]]++; } else { act[b[v]]++; } } void dec(int v) { if (b[v] < BLOCK) { c[b[v]]--; } else { act[b[v]]--; } } void add(int i) { int v = a[i]; dec(v); b[v]++; inc(v); } void remove(int i) { int v = a[i]; dec(v); b[v]--; inc(v); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; for (ll i = 1; i <= n; i++) { negyzet[i] = negyzet[i-1] + i*i; } for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<Query> qrys(q); for (int i = 0; i < q; i++) { cin >> qrys[i].l >> qrys[i].r; qrys[i].idx = i+1; } sort(qrys.begin(), qrys.end()); int l = 1, r = 0; for (auto [nl, nr, idx] : qrys) { while (r < nr) add(++r); while (r > nr) remove(r--); while (l < nl) remove(l++); while (l > nl) add(--l); deque<pair<ll, ll>> dq; int d = 0; auto push = [&](int a, int b) { if (d) dq.emplace_back(a, b); else dq.emplace_front(a, b); d ^= 1; }; for (auto it = act.rbegin(); it != act.rend(); it++) { auto [len, cnt] = *it; if (cnt == 0) continue; if (cnt & 1) { push(len, 1); cnt--; } push(len, cnt/2); push(len, cnt/2); } for (int i = BLOCK-1; i >= 1; i--) { int len = i, cnt = c[i]; if (cnt == 0) continue; if (cnt & 1) { push(len, 1); cnt--; } push(len, cnt/2); push(len, cnt/2); } for (auto it = act.begin(); it != act.end();) { auto [len, cnt] = *it; if (cnt == 0) { it = act.erase(it); } else { it++; } } auto sum_arit = [&](ll start, ll d, ll cnt) { return start*cnt + d * (cnt - 1) * cnt / 2; }; ll pref = 0; int x = nr-nl+1; for (auto [len, cnt] : dq) { ans[idx] += cnt * (len*(len+1)/2); ans[idx] += cnt * (len*(x-len)); ans[idx] += (x - len) * sum_arit(pref, len, cnt); ans[idx] -= pref * pref * cnt; ans[idx] -= pref * sum_arit(0, 2*len, cnt); ans[idx] -= len * len * negyzet[cnt-1]; pref += len*cnt; } } for (int i = 1; i <= q; i++) { cout << ans[i] << "\n"; } return 0; }

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:68:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for (auto [nl, nr, idx] : qrys) {
      |               ^
diversity.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |             auto [len, cnt] = *it;
      |                  ^
diversity.cpp:107:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |             auto [len, cnt] = *it;
      |                  ^
diversity.cpp:121:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for (auto [len, cnt] : dq) {
      |                   ^
#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...