#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
const int Q = 5e4 + 11;
const int B = 500;
long long solve(vector<pair<int, int>> c) {
reverse(c.begin(), c.end());
int n = 0, k = 0;
deque<pair<int, int>> q;
int t = 0;
for (const auto &[x, y] : c) {
n += x * y;
k += y;
if (t) {
q.push_back({x, (y + 1) / 2});
if (y > 1)
q.push_front({x, y / 2});
} else {
q.push_front({x, (y + 1) / 2});
if (y > 1)
q.push_back({x, y / 2});
}
t = (t + y) & 1;
}
long long all = n * 1ll * (n + 1) / 2 * k;
long long bad = 0;
long long sum = 0;
for (int i = 0; i < (int) q.size(); ++i) {
const auto &[x, y] = q[i];
bad += sum * sum * y;
bad += sum * x * y * (y - 1);
bad += sum * y;
bad += x * y * (y - 1);
bad += (y - 1) * y * (2 * y - 1) / 6 * x * x;
sum += x * y;
}
sum = 0;
for (int i = (int) q.size() - 1; i >= 0; --i) {
const auto &[x, y] = q[i];
bad += sum * sum * y;
bad += sum * x * y * (y - 1);
bad += sum * y;
bad += x * y * (y - 1);
bad += (y - 1) * y * (2 * y - 1) / 6 * x * x;
sum += x * y;
}
bad /= 2;
long long res = all - bad;
return res;
}
int n, q;
int a[N];
int l[Q], r[Q];
int ord[Q];
struct Cnt {
int cnt[N];
int scnt[N];
set<int> s;
void add(int x) {
if (--scnt[cnt[x]] == 0)
s.erase(cnt[x]);
++cnt[x];
if (++scnt[cnt[x]] == 1)
s.insert(cnt[x]);
}
void remove(int x) {
if (--scnt[cnt[x]] == 0)
s.erase(cnt[x]);
--cnt[x];
if (++scnt[cnt[x]] == 1)
s.insert(cnt[x]);
}
vector<pair<int, int>> get_cnts() {
vector<pair<int, int>> res;
res.reserve(s.size());
for (const auto &i : s) {
if (i != 0)
res.push_back({i, scnt[i]});
}
assert(is_sorted(res.begin(), res.end()));
return res;
}
Cnt() {
for (int i = 0; i < N; ++i) {
++scnt[cnt[i]];
}
s.insert(0);
}
} cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i];
--l[i];
}
iota(ord, ord + q, 0);
sort(ord, ord + q, [&] (const int &i, const int &j) {
return make_pair(l[i] / B, r[i]) < make_pair(l[j] / B, r[j]);
});
vector<long long> ans(q);
int cl = 0, cr = 0;
for (int i = 0; i < q; ++i) {
while (cl > l[ord[i]]) {
cnt.add(a[--cl]);
}
while (cr < r[ord[i]]) {
cnt.add(a[cr++]);
}
while (cl < l[ord[i]]) {
cnt.remove(a[cl++]);
}
while (cr > r[ord[i]]) {
cnt.remove(a[--cr]);
}
ans[ord[i]] = solve(cnt.get_cnts());
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
14 ms |
1000 KB |
Output is correct |
5 |
Correct |
27 ms |
1740 KB |
Output is correct |
6 |
Correct |
43 ms |
2380 KB |
Output is correct |
7 |
Correct |
37 ms |
2664 KB |
Output is correct |
8 |
Correct |
41 ms |
2268 KB |
Output is correct |
9 |
Correct |
43 ms |
2328 KB |
Output is correct |
10 |
Correct |
41 ms |
2488 KB |
Output is correct |
11 |
Correct |
43 ms |
2380 KB |
Output is correct |
12 |
Correct |
42 ms |
2348 KB |
Output is correct |
13 |
Correct |
43 ms |
2316 KB |
Output is correct |
14 |
Correct |
43 ms |
2352 KB |
Output is correct |
15 |
Correct |
41 ms |
2412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
14 ms |
1000 KB |
Output is correct |
5 |
Correct |
27 ms |
1740 KB |
Output is correct |
6 |
Correct |
43 ms |
2380 KB |
Output is correct |
7 |
Correct |
37 ms |
2664 KB |
Output is correct |
8 |
Correct |
41 ms |
2268 KB |
Output is correct |
9 |
Correct |
43 ms |
2328 KB |
Output is correct |
10 |
Correct |
41 ms |
2488 KB |
Output is correct |
11 |
Correct |
43 ms |
2380 KB |
Output is correct |
12 |
Correct |
42 ms |
2348 KB |
Output is correct |
13 |
Correct |
43 ms |
2316 KB |
Output is correct |
14 |
Correct |
43 ms |
2352 KB |
Output is correct |
15 |
Correct |
41 ms |
2412 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
340 KB |
Output is correct |
18 |
Correct |
3 ms |
340 KB |
Output is correct |
19 |
Correct |
16 ms |
1072 KB |
Output is correct |
20 |
Correct |
33 ms |
1756 KB |
Output is correct |
21 |
Correct |
50 ms |
2568 KB |
Output is correct |
22 |
Correct |
46 ms |
2380 KB |
Output is correct |
23 |
Correct |
48 ms |
2468 KB |
Output is correct |
24 |
Correct |
46 ms |
2316 KB |
Output is correct |
25 |
Correct |
47 ms |
2396 KB |
Output is correct |
26 |
Correct |
49 ms |
2352 KB |
Output is correct |
27 |
Correct |
47 ms |
2408 KB |
Output is correct |
28 |
Correct |
48 ms |
2500 KB |
Output is correct |
29 |
Correct |
49 ms |
2388 KB |
Output is correct |
30 |
Correct |
50 ms |
2468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
14 ms |
1000 KB |
Output is correct |
5 |
Correct |
27 ms |
1740 KB |
Output is correct |
6 |
Correct |
43 ms |
2380 KB |
Output is correct |
7 |
Correct |
37 ms |
2664 KB |
Output is correct |
8 |
Correct |
41 ms |
2268 KB |
Output is correct |
9 |
Correct |
43 ms |
2328 KB |
Output is correct |
10 |
Correct |
41 ms |
2488 KB |
Output is correct |
11 |
Correct |
43 ms |
2380 KB |
Output is correct |
12 |
Correct |
42 ms |
2348 KB |
Output is correct |
13 |
Correct |
43 ms |
2316 KB |
Output is correct |
14 |
Correct |
43 ms |
2352 KB |
Output is correct |
15 |
Correct |
41 ms |
2412 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
340 KB |
Output is correct |
18 |
Correct |
3 ms |
340 KB |
Output is correct |
19 |
Correct |
16 ms |
1072 KB |
Output is correct |
20 |
Correct |
33 ms |
1756 KB |
Output is correct |
21 |
Correct |
50 ms |
2568 KB |
Output is correct |
22 |
Correct |
46 ms |
2380 KB |
Output is correct |
23 |
Correct |
48 ms |
2468 KB |
Output is correct |
24 |
Correct |
46 ms |
2316 KB |
Output is correct |
25 |
Correct |
47 ms |
2396 KB |
Output is correct |
26 |
Correct |
49 ms |
2352 KB |
Output is correct |
27 |
Correct |
47 ms |
2408 KB |
Output is correct |
28 |
Correct |
48 ms |
2500 KB |
Output is correct |
29 |
Correct |
49 ms |
2388 KB |
Output is correct |
30 |
Correct |
50 ms |
2468 KB |
Output is correct |
31 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |