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>
typedef long long ll;
using namespace std;
const int NMAX = 3e5;
int aib[NMAX + 5];
int n;
void update (int pos, const int &val)
{
for (; pos <= n; pos += pos & -pos)
aib[pos] += val;
}
int query (int pos)
{
int ret = 0;
for (; pos; pos -= pos & -pos)
ret += aib[pos];
return ret;
}
ll a[NMAX + 5];
ll b[NMAX + 5];
ll ans[NMAX + 5];
int main()
{
cin >> n;
for (int i=1; i<=n; i++)
{
cin >> a[i];
b[i] = a[i];
}
sort (b+1, b+n+1);
for (int i=1; i<=n; i++)
{
a[i] = lower_bound(b+1, b+n+1, a[i]) - (b + 1) + 1;
}
for (int i=1; i<=n; i++)
{
ans[i] = query(a[i] - 1);
update(a[i], +1);
}
memset(aib, 0, sizeof(aib));
for (int i=n; i>0; i--)
{
ans[i] *= query(a[i] - 1);
update(a[i], +1);
}
ll sum = 0;
for (int i=1; i<=n; i++)
sum += ans[i];
cout << sum;
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... |