Submission #798550

#TimeUsernameProblemLanguageResultExecution timeMemory
798550JohannDiversity (CEOI21_diversity)C++14
4 / 100
1 ms340 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<int> vi; #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 P; vi answerPermutation; 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; int n = r - l; A = vi(AA.begin() + l, AA.begin() + r); vi heatMap(*max_element(all(A)) + 1, 0); for (int i = 0; i < sz(A); ++i) ++heatMap[A[i]]; vi cnts; for (int i = 0; i < sz(heatMap); ++i) if (heatMap[i]) cnts.push_back(heatMap[i]); sort(all(cnts)); ll num = sz(cnts); ans = INF; for (int i = 0; i < (1 << num); ++i) { // if all were different ll tmp = n * (n + 1) * (n + 1) / 2 - (2 * n + 1) * (n + 1) * n / 6; ll right = 0; ll left = 0; for (int j = 0; j < num; ++j) { ll x = cnts[j]; // either with left or right endpoint in set tmp -= (n - x) * x * (x - 1) / 2; // if both are in set tmp -= x * x * (x - 1) / 2 - (2 * x - 1) * x * (x - 1) / 6; if (i & (1 << j)) { // left tmp -= (x - 1) * left * (n - left - x); left += x; } else { // right tmp -= (x - 1) * right * (n - right - x); right += x; } } ans = min(ans, tmp); } 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...