This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
ll 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |