Submission #1883314

---

Source Code Expand

#include<iostream>
#include <algorithm>
using namespace std;
struct node{
	long long num;
	int id;
	int numx;
}a[200007];
node b[200007];
long long tree[200007];
inline int lowbit(int x) {
	return (x & -x);
}
void add(int x, int v) {
	for (int i = x; i <= 200007; i += lowbit(i)) {
		tree[i] += v;
	}
}
long long get(int x) {
	long long sum = 0;
	for (int i = x; i  ; i -= lowbit(i)) {
		sum += tree[i];
	}
	return sum;
}
int cmp(node a,node b){
	return a.num<b.num;
}
int cmp2(node a,node b){
	return a.id<b.id;
}
int main() {
	ios::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	b[0].num=a[0].num=0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].num;
		a[i].num-=k;
		a[i].id=i;
		b[i].num=b[i-1].num+a[i].num;
		b[i].id=i;
	}
	b[0].id=0;
	sort(b,b+1+n,cmp);
	int t=1;
	b[0].numx=1;
	for (int i = 1; i <=n ; ++i)
	{	
		b[i].numx=b[i].num==b[i-1].num?t:++t;
	  
	}
	sort(b,b+1+n,cmp2);
	int sum=0;
	for (int i = 0; i <=n ; ++i)
	{
	//cout<<a[i].num<<" "<<b[i].num<<" "<<b[i].numx<<endl;	
	}

	for(int i=n;i>=0;i--){

		
	//	cout<<i<<" "<<b[i].numx-1<<" "<<get(n+1)<<" "<<get(b[i].numx-1)<<endl;
		sum+=get(n+1)-get(b[i].numx-1);
		add(b[i].numx,1);
	}

	cout << sum << endl;
}

Submission Info

Judge Result