Submission #1686807

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = 1e9 + 7;
const int INF = 1e9;
const int MAX_N = 200002;
//BIT	[1,n]
int bit[MAX_N + 1], siz;
int sum(int i){
	int s = 0;
	while (i > 0) {
		s += bit[i];
		i -= i&-i;//最後の1bit
	}
	return s;
}
void add(int i, int x){
	while (i <= siz) {
		bit[i] += x;
		i += i&-i;//最後の1bit
	}
}


int main() {
	cin.sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<ll>b(N+1),tmp(N+1);
	map<ll, int>mp;
	b.push_back(0);
	reps(i,1, N+1) {
		ll a;
		cin >> a;
		b[i] = b[i-1]+a - K;
		tmp[i] = b[i];
		mp[b[i]] = 0;
	}
	sort(tmp.begin(), tmp.end());
	rep(i, N + 1)mp[tmp[i]] = i;
	int ans = 0;
	siz = N + 1;
	rep(i, N + 1) {
		ans += sum(mp[b[i]] + 1);
		add(mp[b[i]] + 1, 1);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result