#include <bits/stdc++.h>
const int N = 3e5 + 5;
struct fenwick {
int t[N];
int query(int i) {
int ans = 0;
for(; i > 0; i -= i & - i) {
ans += t[i];
}
return ans;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
void update(int i, int v) {
for(; i < N; i += i & - i) {
t[i] += v;
}
}
void update(int l, int r, int v) {
update(l, v);
update(r + 1, - v);
}
}fenwick;
int main() {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<int> compres;
for(int i = 1; i <= n; i++) {
compres.push_back(a[i]);
}
std::sort(compres.begin(), compres.end());
compres.erase(unique(compres.begin(), compres.end()), compres.end());
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(compres.begin(), compres.end(), a[i]) - compres.begin() + 1;
}
int64_t ans = 0;
std::vector<int> p(n + 1), s(n + 1);
for(int i = 1; i <= n; i++) {
p[i] = fenwick.query(a[i] - 1);
fenwick.update(a[i], 1);
}
for(int i = 1; i <= n; i++) {
fenwick.update(a[i], - 1);
}
for(int i = n; i >= 1; i--) {
s[i] = fenwick.query(a[i] - 1);
fenwick.update(a[i], 1);
}
for(int i = 1; i <= n; i++) {
ans += p[i] * s[i];
}
std::cout << ans;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |