#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Fenwick {
int n;
vector<ll> f;
Fenwick(int _n): n(_n), f(n+1, 0) {}
void update(int i, ll v) {
for (; i <= n; i += i&-i) f[i] += v;
}
ll query(int i) {
ll s = 0;
for (; i > 0; i -= i&-i) s += f[i];
return s;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ll> B(N);
for(int i = 0; i < N; i++){
ll a;
cin >> a;
B[i] = a + 2LL * i;
}
// Coordinate‐compress B so we can index the Fenwick tree
vector<ll> vals = B;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
Fenwick fw(vals.size());
ll ans = 0;
// We iterate left-to-right; at each B[i], we want
// # of previous B[j] > B[i] = total_seen - # of previous ≤ B[i]
for(int i = 0; i < N; i++){
int pos = int(lower_bound(vals.begin(), vals.end(), B[i]) - vals.begin()) + 1;
ll seen_le = fw.query(pos);
ll seen_tot = i;
ans += (seen_tot - seen_le);
fw.update(pos, 1);
}
cout << ans << "\n";
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... |