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;
using ll = long long;
using pii = pair<ll,ll>;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
ll n, q; cin >> n >> q;
vector<ll> arr(n);
for (ll i = 0; i < n; ++i) {
cin >> arr[i];
}
for (ll i = 0; i < q; ++i) {
ll l, r; cin >> l >> r;
l--;
vector<ll> v;
vector<ll> app(300002);
v.reserve(r - l);
ll s = r - l;
for (ll j = l; j < r; ++j) {
v.push_back(arr[j]);
}
for (auto x : v) {
app[x]++;
}
vector<pii> v2;
for (auto x : v) {
v2.emplace_back(app[x],x);
}
std::sort(v2.begin(), v2.end());
vector<pii> orderA, orderB;
ll last = -1;
ll leftS = 0, rightS = 0;
for (auto [a, x] : v2) {
if (last != x) {
if (leftS <= rightS) {
orderA.emplace_back(x, a);
leftS += a;
}
else {
orderB.emplace_back(x,a);
rightS += a;
}
}
last = x;
}
vector<pii> order;
for (auto x : orderA) {
order.push_back(x);
}
std::reverse(orderB.begin(), orderB.end());
for (auto x : orderB) {
order.push_back(x);
}
ll a = 0;
ll ans = 0;
for (auto [x, amount] : order) {
ll b = a + amount;
ll includeSub = a * (s - b);
ll includePar = a * amount + (s - b) * amount;
ll self = amount * (amount + 1) / 2;
ans += self + includePar + includeSub;
a += amount;
}
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... |