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>
using namespace std;
#define ll long long
ll h[300005];
ll hh[300005];
map <ll, int> mp;
int v[300005];
int seg[12000005];
void update(int nod, int l, int r, int poz, int val)
{
int mid;
if (r == l)
{
seg[nod] += val;
return;
}
mid = (l + r) / 2;
if (poz <= mid)
update (2 * nod, l, mid, poz, val);
else
update (2 * nod + 1, mid + 1, r, poz, val);
seg[nod] = seg[2 * nod] + seg[2 * nod + 1];
}
int query (int nod, int l, int r, int ql, int qr)
{
int mid;
if (ql <= l&& r <= qr)
return seg[nod];
mid = (l + r) / 2;
int s = 0;
if (mid >= ql)
s += query(2 * nod, l, mid, ql, qr);
if (mid < qr)
s += query(2 * nod + 1, mid + 1, r, ql, qr);
return s;
}
int d[300005];
int main()
{
int n, i;
ll ans = 0;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> h[i];
hh[i] = h[i];
}
sort (hh + 1, hh + n + 1);
mp[hh[1]] = 1;
int l = 1;
for (i = 2; i <= n; i++)
{
if (hh[i] != hh[i - 1])
{
l++;
mp[hh[i]] = l;
}
}
for (i = 1; i <= n; i++)
v[i] = mp[h[i]];
for (i = 1; i <= n; i++)
{
if (v[i] - 1)
d[i] = query(1, 1, n, 1, v[i] - 1);
update(1, 1, n, v[i], 1);
}
for (i = 1; i <= 4 * n; i++)
seg[i] = 0;
for (i = n; i; i--)
{
if (v[i] - 1)
ans += 1LL * query(1, 1, n, 1, v[i] - 1) * d[i];
update(1, 1, n, v[i], 1);
}
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... |