# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1268157 | TgX_2 | Vudu (COCI15_vudu) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 7;
int n, p, a[maxn];
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int _n) {
n = _n;
bit.assign(n + 5, 0);
}
void add(int i, int val) {
for (; i <= n; i += i & -i) bit[i] += val;
}
int sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("temp.inp", "r")) {
freopen("temp.inp", "r", stdin);
freopen("temp.out", "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> p;
vector<int> val;
for (int i = 1; i <= n; i++) {
a[i] -= p;
a[i] += a[i - 1];
val.push_back(a[i]);
}
val.push_back(0);
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for (int i = 1; i <= n; i++)
a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
int m = (int)(val.size()) + 1;
Fenwick fen(m);
int ans = 0;
fen.add(lower_bound(val.begin(), val.end(), 0) - val.begin() + 1, 1);
for (int i = 1; i <= n; i++) {
ans += fen.sum(a[i]);
fen.add(a[i], 1);
}
cout << ans;
cerr << "Time : " << clock() * 1.0 / CLOCKS_PER_SEC << " ms." << endl;
return 0;
}