Submission #1867979

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, k;
long long a[N];
vector<long long> z;
long long ans;

// BIT
int T[N];
void upd(int x) { for (; x < N; x += x & -x) T[x]++; }
int get(int x) { int res = 0; for (; x > 0; x -= x & -x) res += T[x]; return res; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i], a[i] -= k;
		a[i] += a[i-1]; // a[] indicates prefix sums now
		z.push_back(a[i]);
	}
	z.push_back(0);
	sort(z.begin(), z.end());
	z.resize(distance(z.begin(), unique(z.begin(), z.end())));

	// solve
	upd(lower_bound(z.begin(), z.end(), 0) - z.begin() + 1);
	for (int i = 1; i <= n; ++i) {
		int pos = lower_bound(z.begin(), z.end(), a[i]) - z.begin() + 1;
		int cur = get(pos);
		ans += cur;
		upd(pos);
	}

	cout << ans << endl;
}

Submission Info

Judge Result