This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int MAXN = 3e5 + 5;
int N, L[MAXN], R[MAXN];
vector <long long> nen;
long long a[MAXN];
struct BIT{
int bit[MAXN];
void upd(int x, int val) {for (; x <= N; x += x &-x) bit[x] += val;}
int get(int x) {
int ans = 0;
for (; x; x -= x&-x) ans += bit[x];
return ans;
}
} mybit;
void calc(int *val) {
FOR(i, 1, N) {
val[i] = mybit.get(a[i] - 1);
mybit.upd(a[i], 1);
}
FOR(i, 1, N) {
mybit.upd(a[i], -1);
}
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//file("TASK");
cin >> N;
FOR(i, 1, N) cin >> a[i], nen.emplace_back(a[i]);
sort(ALL(nen)); nen.erase(unique(ALL(nen)), nen.end());
FOR(i, 1, N) a[i] = lower_bound(ALL(nen), a[i]) - nen.begin() + 1;
calc(L);
reverse(a + 1, a + N + 1);
calc(R);
reverse(R + 1, R + N + 1);
long long ans = 0;
FOR(i, 1, N) ans += 1ll * L[i] * R[i];
cout << ans;
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 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... |