Submission #2207569

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;

lli n,k;
vll a;
lli ans = 0;
map<lli,lli> zip;

class bit {
private:
	vll* v;
	lli n;
public:
	bit (lli n) {
		this->v = new vll(n+1);
		this->n = n;
	}
	void add(lli i,lli val){
		for(;i <= n;i += i&-i) this->v->at(i) += val;
	}
	lli sum(lli i){
		lli ret = 0;
		for(;i > 0;i -= i&-i) ret += this->v->at(i);
		return ret;
	}
};

int main(){
	cin >> n >> k;
	a = vll(n+1);
	for(lli i = 1;i <= n;i++) cin >> a[i];
	for(lli i = 1;i <= n;i++) a[i] -= k;
	for(lli i = 0;i < n;i++) a[i+1] += a[i];
	// for(lli i = 0;i <= n;i++){
	// 	for(lli j = i+1;j <= n;j++){
	// 		if(a[j] >= a[i]) ans++;
	// 	}
	// }
	for(lli i = 0;i <= n;i++) zip[a[i]] = 0;
	lli i = 1;
	for(auto itr = zip.begin();itr != zip.end();itr++){
		itr->second = i;
		i++;
	}
	bit b = bit(n+1);
	for(lli i = n;i >= 0;i--){
		ans += b.sum(n+1)-b.sum(zip[a[i]]-1);
		b.add(zip[a[i]],1);
	}
	cout << ans << endl;
	return 0;

}

Submission Info

Judge Result