#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct stree {
#define lc v*2
#define rc v*2+1
vector <int> tree;
stree (int s) {
tree.resize(s*4);
}
void pushup(int v) {
tree[v] = tree[lc] + tree[rc];
}
void update(int v, int tl, int tr, int p) {
if (tl > p || tr < p)
return;
if (tl == tr) {
tree[v] = 1;
return;
}
int tm = (tl + tr) / 2;
update(lc, tl, tm, p);
update(rc, tm+1, tr, p);
pushup(v);
}
int query(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
if (tl >= l && tr <= r)
return tree[v];
int tm = (tl + tr) / 2;
int a = query(lc, tl, tm, l, r);
int b = query(rc, tm+1, tr, l, r);
return a + b;
}
};
int main() {
int n;
cin >> n;
map <ll, vector <int>> mp;
for (int i = 0; i < n; i++) {
ll x;
cin >> x;
mp[x].push_back(i);
}
stree tree(n);
ll ans = 0;
for (auto it : mp) {
for (auto i : it.second) {
ll l = tree.query(1, 0, n, 0, i);
ll r = tree.query(1, 0, n, i, n);
ans += l * r;
}
for (auto i : it.second) {
tree.update(1, 0, n, i);
}
}
cout << ans << '\n';
}
# | 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... |