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 <vector>
#include <algorithm>
using namespace std;
const int maxN = 300'000;
int H[1+maxN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for(int i = 1; i <= N; i++) cin >> H[i];
vector<int> ind(N);
for(int i = 1; i <= N; i++) ind[i-1] = i;
sort(ind.begin(), ind.end(), [] (int p, int q)
{
if(H[p] == H[q]) return p > q;
return H[p] < H[q];
});
vector<long long> lft(1+N, 0), rgt(1+N, 0);
vector<int> BIT(1+N, 0);
for(int i: ind)
{
for(int j = i; j <= N; j += j&-j)
BIT[j]++;
for(int j = i-1; j >= 1; j -= j&-j)
lft[i] += BIT[j];
}
// cerr << "check\n";
BIT = vector<int>(1+N, 0);
sort(ind.begin(), ind.end(), [] (int p, int q)
{
if(H[p] == H[q]) return p < q;
return H[p] < H[q];
});
// cerr << "check\n";
for(int i: ind)
{
for(int j = i; j <= N; j += j&-j)
BIT[j]++;
for(int j = N; j >= 1; j -= j&-j)
rgt[i] += BIT[j];
for(int j = i; j >= 1; j -= j&-j)
rgt[i] -= BIT[j];
}
// for(int i = 1; i <= N; i++) cerr << lft[i] << ' ';
// cerr << '\n';
long long ans = 0;
for(int i = 1; i <= N; i++) ans += lft[i] * rgt[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... |