| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 75543 | noclever | Vudu (COCI15_vudu) | C++14 | 0 ms | 0 KiB |
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>
#include <map>
using namespace std;
template<typename T>
class fenwick {
private:
int n;
vector<T> fenw;
public:
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
vector<long long> b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long p;
cin >> p;
for (int i = 0; i < n; i++) {
a[i] -= p;
}
b[0] = a[0];
for (int i = 1; i < n; i++) {
a[i] += a[i - 1];
b[i] = a[i];
}
sort(unique(b.begin(), b.end()));
map<long long, int> mp;
for (int i = 0; i < n; i++) {
mp[a[i]] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}
fenwick<long long> fenw(n);
long long ans = 0ll;
for (int i = 0; i < n; i++) {
if (a[i] >= 0) {
ans++;
}
int tmp = mp[a[i]];
ans += (fenw.get(tmp));
fenw.modify(tmp, +1);
}
cout << ans << endl;
return 0;
}