#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<pair<long long, int>, __gnu_pbds::null_type, less<pair<long long, int>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
vector<int> x(n);
for(int i = 0; i < n; i++){
cin >> x[i];
}
int k; cin >> k;
for(int i = 0; i < n; i++){
x[i] -= k;
}
vector<long long> pref(n+1);
ll sum = 0;
for(int i = 1; i <= n; i++){
sum += x[i-1];
pref[i] = sum;
}
sum = 0;
ordered_set o;
o.insert({0, -1});
for(int i = 0; i < n; i++){
sum += o.order_of_key({pref[i+1], n+1});
o.insert({pref[i+1], i});
}
cout << sum << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |