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 <iostream>
#include <map>
#define int long long
using namespace std;
const int nmax = 3e5 + 7;
int dr[nmax], st[nmax], f[nmax], v[nmax];
map<int, int> mp;
void update(int i) {
int val = 1;
while(i < nmax) {
f[i] += val;
i += (i & (-i));
}
}
int query(int i) {
int sum = 0;
while(i > 0) {
sum += f[i];
i -= (i & (-i));
}
return sum;
}
int32_t main() {
int n;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> v[i];
mp[v[i]];
}
int cnt = 2;
for(auto &it : mp) {
it.second = cnt;
cnt ++;
}
for(int i = 1; i <= n; i ++) {
v[i] = mp[v[i]];
}
for(int i = 1; i <= n; i ++) {
dr[i] = query(v[i] - 1);
update(v[i]);
}
for(int i = 0; i < nmax; i ++) {
f[i] = 0;
}
for(int i = n; i >= 1; i --) {
st[i] = query(v[i] - 1);
update(v[i]);
}
long long ans = 0;
for(int i = 1; i <= n; i ++) {
ans += dr[i] * st[i];
}
cout << ans;
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |