Submission #2873171

---

Source Code Expand

#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#include<fstream>

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define ll long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;

const ll MOD = 1000000007;// 10^9+7
const int INF = (1 << 30);
constexpr int MAX_N = 200005;

struct BIT {
	int n;
	vector<ll> bit;

	BIT(int n_) {
		n_++;
		n = n_;
		bit.resize(MAX_N);
		REP(i, n)add(i, 1);
	}
	ll sum(ll i) {
		i++;
		ll s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
	void add(ll i, ll x) {
		i++;
		while (i <= n) {
			bit[i] += x;
			i += i & -i;
		}
	}
};

//変数
int N;
ll K;
vector<ll> a;






//サブ関数
//入力
void input()
{
	cin >> N >> K;
	a.resize(N + 1);
	REP(i, N)cin >> a[i + 1];
	REP(i, N)a[i + 1] -= K;
	REP(i, N)a[i + 1] += a[i];
}

vector<pair<ll, ll>> make_sample(vector<ll> a)
{
	vector<pair<ll, ll>> sample;
	REP(i, N + 1)sample.push_back({ a[i],i });
	sort(sample.begin(), sample.end());
	return sample;
}


ll count(
	vector<pair<ll, ll>>& sample,
	BIT& bit,
	pair<ll, ll> alpha)
{
	auto itr = lower_bound(sample.begin(), sample.end(), alpha);
	if (alpha != *itr)exit(1);
	int id = distance(sample.begin(), itr);

	int res = bit.sum(N) - bit.sum(id);
	bit.add(id, -1);
	return res;
}

//計算
void calc()
{
	ll res = 0;
	BIT bit(N);
	auto sample = make_sample(a);

	REP(i, N+1)res += count(sample, bit, { a[i],i });

	cout << res << endl;
}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	output();
	debug();
	
	return 0;
}

Submission Info

Judge Result