Submission #799359

#TimeUsernameProblemLanguageResultExecution timeMemory
799359JohannDiversity (CEOI21_diversity)C++14
64 / 100
7059 ms18348 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<ll> vi; typedef pair<ll, ll> pii; typedef vector<pii> vpii; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const ll INF = 1e18; int N, Q; vi A; vi ans; vi heatmap; multiset<int> cnts; struct query { int l, r, idx; }; ll numberOfSubsequences(ll n) { return n * (n + 1) / 2; } ll totalLengthOfSubsequences(ll n) { return n * (n + 1) * (n + 1) / 2 - (2 * n + 1) * (n + 1) * n / 6; } void add(int x) { if (heatmap[x] > 0) { auto it = cnts.find(heatmap[x]); cnts.erase(it); } ++heatmap[x]; cnts.insert(heatmap[x]); } void sub(int x) { auto it = cnts.find(heatmap[x]); cnts.erase(it); --heatmap[x]; if (heatmap[x]) cnts.insert(heatmap[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> Q; A.resize(N); for (int i = 0; i < N; ++i) cin >> A[i]; vector<query> Qu(Q); ans.resize(Q); for (int i = 0; i < Q; ++i) cin >> Qu[i].l >> Qu[i].r, Qu[i].idx = i, --Qu[i].l; int sq = 1; while (sq * sq < N) ++sq; auto cmp = [&](const query &a, const query &b) { if (a.l / sq == b.l / sq) return a.r < b.r; else return a.l < b.l; }; sort(all(Qu), cmp); int lx = 0, rx = 0; heatmap.assign(*max_element(all(A)) + 1, 0); for (query q : Qu) { while (rx < q.r) add(A[rx++]); while (lx > q.l) add(A[--lx]); while (rx > q.r) sub(A[--rx]); while (lx < q.l) sub(A[lx++]); ll n = q.r - q.l; ll left = 0, right = 0; ll tmp = totalLengthOfSubsequences(n); for (auto it = cnts.begin(); it != cnts.end(); ++it) { ll x = *it; // how much ll y = 1; // how often ll len = x * y; // if both are in set tmp -= totalLengthOfSubsequences(len) - x * x * (totalLengthOfSubsequences(y) - y) - y * numberOfSubsequences(x); // if one is inside the other isn't tmp -= (n - len) * (len * (len + 1) / 2 - x * y * (y + 1) / 2); // if both are outside tmp -= (len - y) * left * (n - left - len); left += len; swap(left, right); } ans[q.idx] = tmp; } for (ll x : ans) cout << x << "\n"; 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...