Problem:
 Score : 600 points    Problem Statement You are given an integer sequence of length N , a = { a_1, a_2, …, a_N }, and an integer K .  a has N(N+1)/2 non-empty contiguous subsequences, { a_l, a_{l+1}, …, a_r } (1 ≤ l ≤ r ≤ N) . Among them, how many have an arithmetic mean that is greater than or equal to K ?      Constraints  All input values are integers.  1 ≤ N ≤ 2 \times 10^5  1 ≤ K ≤ 10^9  1 ≤ a_i ≤ 10^9         Input Input is given from Standard Input in the following format:  N  K  a_1  a_2  :  a_N       Output Print the number of the non-empty contiguous subsequences with an arithmetic mean that is greater than or equal to K .        Sample Input 1 3 6
7
5
7      Sample Output 1 5  All the non-empty contiguous subsequences of a are listed below:   { a_1 } = { 7 }  { a_1, a_2 } = { 7, 5 }  { a_1, a_2, a_3 } = { 7, 5, 7 }  { a_2 } = { 5 }  { a_2, a_3 } = { 5, 7 }  { a_3 } = { 7 }   Their means are 7 , 6 , 19/3 , 5 , 6 and 7 , respectively, and five among them are 6 or greater. Note that { a_1 } and { a_3 } are indistinguishable by the values of their elements, but we count them individually.       Sample Input 2 1 2
1      Sample Output 2 0       Sample Input 3 7 26
10
20
30
40
30
20
10      Sample Output 3 13

Solution (Python):
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*(n+5)
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)

Solution (Python):
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from itertools import accumulate,repeat

N,K = map(int, input().split())

B = [0] + [sa-sk for sa,sk in zip(accumulate(int(input()) for _ in range(N)), accumulate(repeat(K)))]

lookup = dict(((b,i+1) for i,b in enumerate(sorted(B))))

result = 0
bit = BinaryIndexedTree(N+1)

for b in B:
  c = lookup[b]
  result += bit.sum(c)
  bit.add(c,1)

print(result)

Solution (Python):
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from bisect import bisect

N,K = map(int, input().split())

A = [int(input()) for i in range(N)]

t = 0
B = [t]
for a in A:
  t += a - K
  B.append(t)

temp = sorted(B)
C = [bisect(temp, b) for b in B]

result = 0
bit = BinaryIndexedTree(N+1)

for c in C:
  result += bit.sum(c)
  bit.add(c,1)

print(result)

Solution (Python):
class BIT():
    def __init__(self,size):
        self.size=size
        self.node=[0]*(size+1)

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

    def add(self,idx,x):
        while idx<=self.size:
            self.node[idx]+=x
            idx+=idx&(-idx)

n,k=map(int,raw_input().split())
a=[int(raw_input()) for _ in xrange(n)]
diff=[]
for i in xrange(n):
    diff.append(a[i]-k)
for i in xrange(n-1):
    diff[i+1]+=diff[i]
bit=BIT(n)
s=set([])
for i in xrange(n):
    s.add(diff[i])
li=list(s)
li.sort()
d={}
for i in xrange(len(li)):
    d[li[i]]=i+1
ans=0
for i in xrange(n):
    pos=d[diff[i]]
    ans+=bit.sum(pos)
    if diff[i]>=0:
        ans+=1
    bit.add(pos,1)
print ans

Solution (Python):
class BIT():
    def __init__(self,size):
        self.size=size
        self.node=[0]*(size+1)

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

    def add(self,idx,x):
        while idx<=self.size:
            self.node[idx]+=x
            idx+=idx&(-idx)

n,k=map(int,raw_input().split())
a=[int(raw_input()) for _ in xrange(n)]
diff=[]
for i in xrange(n):
    diff.append(a[i]-k)
for i in xrange(n-1):
    diff[i+1]+=diff[i]
bit=BIT(n)
s=set([])
for i in xrange(n):
    bit.add(i+1,1)
    s.add(diff[i])
li=list(s)
li.sort()
d={}
for i in xrange(len(li)):
    d[li[i]]=i
pos=[[] for _ in xrange(len(li))]
for i in xrange(n):
    idx=d[diff[i]]
    pos[idx].append(i+1)
ans=0
for i in xrange(len(li)):
    for j in pos[i]:
        ans+=bit.sum(n)-bit.sum(j)
        if diff[j-1]>=0:
            ans+=1
        bit.add(j,-1)
print ans

Solution (Python):
import sys
from itertools import accumulate

inf = 1<<60
ans = 0

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = [int(sys.stdin.readline().rstrip()) - k for i in range(n)]
    s = [0] + list(accumulate(a))

    MergeSort(s)

    print(ans)

def MergeSort(a):
    if len(a) == 1:
        return a

    apre = MergeSort(a[:len(a)//2])
    asuf = MergeSort(a[len(a)//2:])

    res = merge(apre, asuf)

    return res

def merge(a, b):
    global ans
    na = len(a)
    nb = len(b)

    a.append(-inf)
    b.append(-inf)

    la = 0
    lb = 0

    res = []

    for i in range(na + nb):
        if a[la] <= b[lb]:
            ans += na - la
            res.append(b[lb])
            lb += 1
        else:
            res.append(a[la])
            la += 1

    return res

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from itertools import accumulate

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = [int(sys.stdin.readline().rstrip()) - k for i in range(n)]
    s = [0] + list(accumulate(a))

    
    s = [(si, i) for (i, si) in enumerate(s)]
    s.sort()

    z = [None] * (n + 1)

    num = -1
    p = -float('inf')

    for i in range(n + 1):
        if s[i][0] > p:
            num += 1

        z[s[i][1]] = num
        p = s[i][0]

    
    ft = FenwickTree(num + 1)

    ans = 0

    for zi in z:
        ans += ft.psum(zi + 1)
        ft.add(zi, 1)

    print(ans)

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.b = [0] * (n + 1)

    def add(self, i, x):
        i += 1

        while i <= self.n:
            self.b[i] += x
            i += i & (-i)

    def psum(self, r):
        res = 0

        while r > 0:
            res += self.b[r]
            r -= r & (-r)

        return res

if __name__ == '__main__':
    solve()

Solution (Python):
n, k = map(int, raw_input().split())
A = [int(raw_input())-k for i in xrange(n)]
su = 0
v = [(0, 0)]
for i in xrange(n):
    su += A[i]
    v.append((su, i+1))
v.sort()

data = [0]*(n+5)
def sum(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= n+2:
        data[i] += x
        i += i & -i
ans = 0
for e, i in v:
    ans += sum(i+1)
    add(i+1, 1)
print ans

Solution (Python):
n, k = map(int, raw_input().split())
A = [int(raw_input())-k for i in xrange(n)]
su = 0
v = [(0, 0)]
for i in xrange(n):
    su += A[i]
    v.append((su, i+1))
v.sort()

data = [0]*(n+5)
def dsum(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= n+2:
        data[i] += x
        i += i & -i
ans = 0
for e, i in v:
    ans += dsum(i+1)
    add(i+1, 1)
print ans