Submission #576854

#TimeUsernameProblemLanguageResultExecution timeMemory
576854talant117408Diversity (CEOI21_diversity)C++17
64 / 100
7072 ms12876 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' const int MAXN = 3e5+7; ll calc(ll n) { return n*(n+1)/2; } ll calc2(ll n) { return n*(n+1)*(2*n+1)/6; } struct MO { vector <int> freq; map <int, int> comp; int N; MO() { N = 0; freq.resize(MAXN); } void add(int n) { if (freq[n]) comp[freq[n]]--; freq[n]++; comp[freq[n]]++; N++; } void remove(int n) { comp[freq[n]]--; freq[n]--; if (freq[n]) comp[freq[n]]++; N--; } ll get() { int saizu = 0; deque <pll> K; for (auto rit = comp.rbegin(); rit != comp.rend(); rit++) { auto x = *rit; if (saizu % 2 == 0) { K.push_front(mp(x.first, (x.second+1)/2)); if (x.second > 1) K.push_back(mp(x.first, x.second/2)); } else { if (x.second > 1) K.push_front(mp(x.first, x.second/2)); K.push_back(mp(x.first, (x.second+1)/2)); } saizu += x.second; } ll l = 0, r; ll ans = 0; for (auto p : K) { int x = p.first, k = p.second; r = N-l-x; ll a = k*calc(x); ll b = k*l + x*calc(k-1); ll c = k*r - x*calc(k-1); ll d = k*l*r + x*(r*calc(k-1) - l*calc(k-1) - x*calc2(k-1)); ans += a + b*x + c*x + d; l += k*x; } return ans; } }; void solve() { int n, q; cin >> n >> q; int BLOCK = sqrt(n); vector <int> v(n); vector <ll> ans(q); vector <pair <pii, int>> queries(q); for (auto &to : v) cin >> to; for (int i = 0; i < q; i++) { cin >> queries[i].first.first >> queries[i].first.second; queries[i].first.first--; queries[i].first.second--; queries[i].second = i; } sort(all(queries), [&](pair <pii, int> a, pair <pii, int> b) { if (a.first.first/BLOCK == b.first.first/BLOCK) { return a.first.second < b.first.second; } return a.first.first/BLOCK < b.first.first/BLOCK; }); int l = 0, r = -1; MO mo; for (auto to : queries) { auto ql = to.first.first, qr = to.first.second, ind = to.second; while (r < qr) { r++; mo.add(v[r]); } while (l > ql) { l--; mo.add(v[l]); } while (r > qr) { mo.remove(v[r]); r--; } while (l < ql) { mo.remove(v[l]); l++; } ans[ind] = mo.get(); } for (auto to : ans) cout << to << endl; } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; }
#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...