# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
648978 | tvladm2009 | 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 <bits/stdc++.h>
#define int ll
using ll = long long;
int const nmax = 1000000;
int v[5 + nmax], sp[5 + nmax];
int index[5 + nmax], aib[5 + nmax];
std::pair<int, int> aux[1 + nmax];
void normalize(int n) {
for(int i = 1;i <= n; i++)
aux[i] = {sp[i], i};
std::sort(aux + 1, aux + n + 1);
int cnt = 1;
index[aux[1].second] = 1;
for(int i = 1;i <= n; i++) {
if(aux[i].first != aux[i - 1].first)
cnt++;
index[aux[i].second] = cnt;
}
}
void update(int x) {
for(int i = x;i <= nmax; i += i & -i)
aib[i]++;
}
int query(int x) {
int ans = 0;
for(int i = x;1 <= i; i -= i & -i)
ans += aib[i];
return ans;
}
signed main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
long long n, p;
std::cin >> n;
for(int i = 1;i <= n; i++)
std::cin >> v[i];
std::cin >> p;
for(int i = 1;i <= n; i++) {
v[i] -= p;
sp[i] = sp[i - 1] + v[i];
}
normalize(n);
ll ans = 0;
for(int i = 1;i <= n; i++) {
ans += query(index[i]);
update(index[i]);
}
for(int i = 1;i <= n; i++) {
if(sp[i] >= 0)
ans++;
}
std::cout << ans;
return 0;
}