Submission #799255

#TimeUsernameProblemLanguageResultExecution timeMemory
799255JohannDiversity (CEOI21_diversity)C++14
64 / 100
7060 ms8900 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, AA; ll ans; vi split(int x) { vi sp; int j = 0; while (2 * (1 << j) <= x) { sp.push_back(1 << j); x -= 1 << j; sp.push_back(1 << j); x -= 1 << j; ++j; } j = 0; while (x > 0) { if (x & (1 << j)) sp.push_back(1 << j), x ^= 1 << j; ++j; } return sp; } 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; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> Q; AA.resize(N); for (int i = 0; i < N; ++i) cin >> AA[i]; while (Q--) { { int l, r; cin >> l >> r; --l; A = vi(AA.begin() + l, AA.begin() + r); } ll n = sz(A); vi heatMap(*max_element(all(A)) + 1, 0); for (int i = 0; i < sz(A); ++i) ++heatMap[A[i]]; map<int, int> cnts; for (int i = 0; i < sz(heatMap); ++i) if (heatMap[i]) ++cnts[heatMap[i]]; vpii S; for (auto it = cnts.begin(); it != cnts.end(); ++it) for (int x : split(it->second)) S.push_back({it->first, x}); ll left = 0, right = 0; int num = sz(S); ans = totalLengthOfSubsequences(n); for (int j = 0; j < num; ++j) { ll x = S[j].first; // how much ll y = S[j].second; // how often for (int i = 0; i < y; ++i) { // if both are in set ans += -totalLengthOfSubsequences(x) + numberOfSubsequences(x); // if on is inside the other isn't ans -= (x - 1) * x / 2 * (n - x); // if both are outside ans -= (x - 1) * left * (n - left - x); left += x; swap(left, right); } } cout << ans << "\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...