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):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, k, x):
        k += 1
        while k <= self.n:
            self.bit[k] += x
            k += k & -k

    def sum(self, k):
        s = 0
        while k > 0:
            s += self.bit[k]
            k -= k & -k
        return s


from collections import defaultdict
N, K = map(int, input().split())
A = []
for i in range(N):
    A.append(int(input()))


B = [0]
s = 0
for i in range(N):
    B.append(s + A[i] - (i + 1) * K)
    s += A[i]

D = [0] * (N + 1)
d = defaultdict(list)
for i in range(len(B)):
    d[B[i]].append(i)

B = sorted(B)
k = 0
i = 0
while i < N + 1:
    m = len(d[B[i]])
    for l in d[B[i]]:
        D[l] = k
    k += 1
    i += m

bt = BIT(N + 1)
num = 0
for i in range(N + 1):
    num += bt.sum(D[i] + 1)
    bt.add(D[i], 1)
print(num)

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

    def add(self, k, x):
        k += 1
        while k <= self.n:
            self.bit[k] += x
            k += k & -k

    def sum(self, k):
        s = 0
        while k > 0:
            s += self.bit[k]
            k -= k & -k
        return s


from collections import defaultdict
N, K = map(int, input().split())
A = []
for i in range(N):
    A.append(int(input()))


B = [0]
s = 0
for i in range(N):
    B.append(s + A[i] - (i + 1) * K)
    s += A[i]

D = [0] * (N + 1)
d = defaultdict(list)
for i in range(len(B)):
    d[B[i]].append(i)

B = sorted(B)
k = 0
i = 0
while i < N + 1:
    m = len(d[B[i]])
    for l in d[B[i]]:
        D[l] = k
    k += 1
    i += m

bt = BIT(N + 1)
num = 0
for i in range(N + 1):
    num += bt.sum(D[i] + 1)
    bt.add(D[i], 1)
print(num)

Solution (Python):
class BIT():

    def __init__(self, n):
        '''
        n = 要素数
        添字は i = 0 ~ n-1 となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        '''i番目の要素にxを加算する'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def get(self, i, j):
        '''[i, j)の和を求める'''
        return self._sum(j) - self._sum(i)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]



cumsum_a = [0]*(n+1)
for i in range(n):
    cumsum_a[i+1] = cumsum_a[i] + a[i]
for i in range(n+1):
    cumsum_a[i] = cumsum_a[i] - k*i


def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    for i in range(len(list1)):
        list1[i] = memo[list1[i]]
    return list1

cumsum_a = compress(cumsum_a)

bit = BIT(n+1)
ans = 0
for i in range(n+1):
    ans += bit.get(0, cumsum_a[i] + 1)
    bit.add(cumsum_a[i], 1)
print(ans)

Solution (Python):
class BIT():

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

    def add(self, i, x):
        '''i番目の要素にxを加算する'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def get(self, i, j):
        '''[i, j)の和を求める'''
        return self._sum(j) - self._sum(i)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]

cumsum_a = [0]*(n+1)
for i in range(n):
    cumsum_a[i+1] = cumsum_a[i] + a[i]
for i in range(n+1):
    cumsum_a[i] = cumsum_a[i] - k*i


def compress(list1):
    len_list1 = len(list1)
    list11 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list11)}
    list2 = [0]*(len_list1)
    for i in range(len_list1):
        list2[i] = memo[list1[i]]
    return list2

cumsum_a = compress(cumsum_a)

bit = BIT(n+1)
ans = 0
for i in range(n+1):
    ans += bit.get(0, cumsum_a[i] + 1)
    bit.add(cumsum_a[i], 1)
print(ans)

Solution (Python):
from itertools import accumulate
import bisect


class Bit():
    def __init__(self, N):
        self.size = N
        self.bit = [0] * (self.size+1)

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

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

    def __str__(self):
        return str(self.bit)


N, K = map(int, input().split())
A = [-10**9] + [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = list(accumulate(diff))
graph = Bit(N+1)
temp = sorted(diff)
order = [bisect.bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += graph.sum(x)
    graph.add(x, 1)

print(ans)

Solution (Python):
from itertools import accumulate
import bisect


class Bit():
    def __init__(self, N):
        self.size = N
        self.bit = [0] * (self.size+1)

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

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

    def __str__(self):
        return str(self.bit)


N, K = map(int, input().split())
A = [-10**9] + [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = list(accumulate(diff))
graph = Bit(N+1)
temp = sorted(diff)
order = [bisect.bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += graph.sum(x)
    graph.add(x, 1)

print(ans)

Solution (Python):
import sys
from copy import deepcopy

F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
A_order = {0}
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
    A_order |= {A[a+1]}
maxA = len(A_order)
A_order = list(A_order)
A_order.sort()

compressed_A = dict()
for i in range(maxA):
    compressed_A[A_order[i]] = i

bit = [0] * (maxA + 1)
total_inversion = 0
for i in range(N+1):
    b = compressed_A[A[i]] + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    
    lower = compressed_A[A[i]] + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += i + 1 - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)

Solution (Python):
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
n,k,*a=map(int,open(0).read().split())
a=[t-k for t in a]
for i in range(1,n):
    a[i]+=a[i-1]
d={}
for i,v in enumerate(sorted(set(a+[0])),1):
    d[v]=i
for i in range(n):
    a[i]=d[a[i]]
b=BIT(max(a))
b.add(d[0],1)
c=0
for p in a:
    c+=b.sum(p)
    b.add(p,1)
print(c)

Solution (Python):
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
n,k,*a=map(int,open(0).read().split())
a=[t-k for t in a]
for i in range(1,n):
    a[i]+=a[i-1]
d={}
for i,v in enumerate(sorted(set(a+[0])),1):
    d[v]=i
for i in range(n):
    a[i]=d[a[i]]
b=BIT(max(a))
b.add(d[0],1)
c=0
for i,p in enumerate(a):
    c+=b.sum(p)
    b.add(p,1)
print(c)

Solution (Python):



class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * n

    def sum(self, i):
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i |= i + 1


def solve(n, a):

    ans = 0

    s = []
    r = 0
    for i in range(n):
        r += a[i]
        s.append((r, i))
        if 0 <= r:
            ans += 1

    s.sort()

    bit = Bit(n)
    for tpl in s:
        _, i = tpl
        ans += bit.sum(i)
        bit.add(i, 1)

    return ans


def main():
    n, k = input().split()
    n = int(n)
    k = int(k)
    a = []
    for _ in range(n):
        ai = input()
        ai = int(ai) - k
        a.append(ai)

    print(solve(n, a))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

def init(As):
    numPow2 = 2 ** (len(As)-1).bit_length()
    data = [0] * (numPow2+1)
    return data, numPow2

def addValue(iA, A):
    iA += 1
    while iA <= numPow2:
        data[iA] += A
        iA += iA & -iA

def getSum(iA):
    iA += 1
    ans = 0
    while iA > 0:
        ans += data[iA]
        iA -= iA & -iA
    return ans


N, K = map(int, input().split())
As = [int(input()) for _ in range(N)]

Bs = list(accumulate([0]+[A-K for A in As]))
iBs = list(range(N+1))
iBs.sort(key=lambda iB: Bs[iB])

data, numPow2 = init([0]*(N+1))

ans = 0
for iB in iBs:
    addValue(iB, 1)
    ans += getSum(iB-1)

print(ans)

Solution (Python):
from itertools import accumulate

class BinaryIndexedTree:
    def __init__(self, As):
        self.numPow2 = 2 ** (len(As)-1).bit_length()
        self.data = [0] * (self.numPow2+1)
        for iA, A in enumerate(As):
            self.addValue(iA, A)

    def addValue(self, iA, A):
        iA += 1
        while iA <= self.numPow2:
            self.data[iA] += A
            iA += iA & -iA

    def getSum(self, iA):
        iA += 1
        ans = 0
        while iA > 0:
            ans += self.data[iA]
            iA -= iA & -iA
        return ans


N, K = map(int, input().split())
As = [int(input()) for _ in range(N)]

Bs = list(accumulate([0]+[A-K for A in As]))
iBs = list(range(N+1))
iBs.sort(key=lambda iB: Bs[iB])

BIT = BinaryIndexedTree([0]*(N+1))

ans = 0
for iB in iBs:
    BIT.addValue(iB, 1)
    ans += BIT.getSum(iB-1)

print(ans)

Solution (Python):
import sys,bisect,math
input = sys.stdin.readline


def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    

def bitadd(bit,i,x):
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit

n,k = map(int,input().split())
a = [int(input()) for i in range(n)]


b = [0]
for i in range(n):
    b.append(b[-1]+a[i])


c = [0]*(n+1)
for i in range(n+1):
    c[i] = b[i]-k*i

d = sorted(c)
for i in range(n+1):
    k = bisect.bisect_left(d,c[i])
    d[k] = d[k]-0.1
    c[i] = k+1

n = n+1
n_ = int(math.log2(n)) + 1
bit = [0] * (2**n_+1)
ass = 0
for j in range(n):
    ass += j-bitsum(bit,c[j])
    
    bit = bitadd(bit,c[j],1)


print(n*(n-1)//2-ass)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        while idx < self.size:
            self.bitree[idx] += val
            idx += idx&(-idx)
            
    def getsum(self, idx:int):
        ret = 0
        while idx > 0:
            ret += self.bitree[idx]
            idx -= idx&(-idx)
            
        return ret
    
    def reset(self):
        self.bitree = [0]*self.size


def val2ord(a: list, rev=False):
    dic = {ai: i for i, ai in enumerate(sorted(a, reverse=rev))}
    return [dic[ai] for ai in a]


n,k = li()
a = [ni() for _ in range(n)]

acc = [0] + list(accumulate(a))

b = [acci - i*k for i,acci in enumerate(acc)]
c = val2ord(b)

bitree = BIT(n+1)

ans = 0
for ci in c:
    bitree.addval(ci+1, 1)
    ans += bitree.getsum(ci+1)-1

print(ans)

Solution (Python):
class BITree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
N,K=map(int,input().split())
a=[int(input()) for i in range(N)]
b=[0 for i in range(N+1)]
for i in range(N):
    b[i+1]=b[i]+a[i]-K
btmp=sorted([(b[i],i) for i in range(N+1)])
c=[-1 for i in range(N+1)]
for i in range(N+1):
    c[btmp[i][1]]=i+1
bit=BITree(N+1)
ans=0
for j in range(N+1):
    ans+=j-bit.sum(c[j])
    bit.add(c[j],1)
print((N*(N+1))//2-ans)

Solution (Python):
from collections import deque
n,k = map(int,input().split())
a = [int(input())-k for i in range(n)]
rui = [0]*(n+1)
for i in range(n):
    rui[i+1] = rui[i] + a[i]
import bisect
def press(a):
    n = len(a)
    b = set(a)
    b = list(b)
    b.sort()
    c = [0] * n
    for i in range(n):
        c[i] = bisect.bisect_left(b,a[i])
    return b,c
b,c = press(rui)
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
bit = BIT(n+2)
ans = 0
for i in c:
    ans += bit.sum(i+1)
    bit.add(i+1,1)
print(ans)

Solution (Python):
def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
def invnumber(n,A):
  S=[0]*n
  A=sorted([(A[i],i) for i in range(n)])
  for i in range(1,n):
     S[A[i][1]]=i
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=S[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return invs
N,K=map(int,input().split())     
A=[int(input())-K for i in range(N)]
T=[0]
for i in range(N):
  T.append(T[-1]+A[i])

print(invnumber(N+1,T))

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def suma(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, K = inpl()
a = [0]
for _ in range(N):
    a.append(a[-1] + int(input()) -K)
c = dict([])
for i, v in enumerate(sorted(set(a))):
    c[v] = i+1
Tr = BIT(N+1)
ans = 0
for v in a:
    ans += Tr.suma(c[v])
    Tr.add(c[v], 1)
print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def suma(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, K = inpl()
a = [0]
for _ in range(N):
    a.append(a[-1] + int(input()) -K)
c = dict([])
for i, v in enumerate(sorted(set(a))):
    c[v] = i+1
Tr = BIT(N+1)
ans = 0
for v in a:
    ans += Tr.suma(c[v])
    Tr.add(c[v], 1)
print(ans)

Solution (Python):
N, K = map(int, input().split())
b = [0]
for _ in range(N):
    b.append(b[-1] + int(input()) - K)


c = {}
for i, v in enumerate(sorted(set(b))):
    c[v] = i + 1


data = [0] * (N + 2)
def add(i):
    while i <= N + 1:
        data[i] += 1
        i += i & -i
def get(i):
    s = 0
    while i:
        s += data[i]
        i -= i & -i
    return s

ans = 0
for v in b:
    ans += get(c[v])
    add(c[v])
print(ans)

Solution (Python):
n,k = (int(i) for i in input().split())
a = [int(input())-k for i in range(n)]
b = [[0,0]]
for i in range(n): b.append([b[-1][0]+a[i],i+1])
b.sort()
num,c = 1,[[b[0][1],1]]
for i in range(1,n+1):
	if b[i][0]!=b[i-1][0]: num+=1
	c.append([b[i][1],num])
c,d,ans = sorted(c),[0]*(n+2),0
def add(i):
	while i<=n+1:
		d[i] += 1
		i += i & -i
def get(i):
	s = 0
	while i:
		s += d[i]
		i -= i & -i
	return s
for i,j in c:
	ans+=get(j)
	add(j)
print(ans)

Solution (Python):
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1=0
        i2=0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
Ak = [a-K for a in A]
Aks = [0]
t = 0
for ak in Ak:
    t += ak
    Aks.append(t)
print(N*(N+1)//2 - mergecount(Aks))

Solution (Python):
from itertools import accumulate
from bisect import bisect_right

N, K = map(int, input().split())
A = [-19] + [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = list(accumulate(diff))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)

temp = sorted(diff)
order = [bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += BIT.sum(x)
    BIT.add(x, 1)

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect_right

N, K = map(int, input().split())
A = [3] + [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = list(accumulate(diff))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)

temp = sorted(diff)
order = [bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += BIT.sum(x)
    BIT.add(x, 1)

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect_right

N, K = map(int, input().split())
A = [0] + [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = list(accumulate(diff))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)

temp = sorted(diff)
order = [bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += BIT.sum(x)
    BIT.add(x, 1)

print(ans)

Solution (Python):
from itertools import accumulate
from bisect import bisect_right

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = [0] + list(accumulate(diff))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)

temp = sorted(diff)
order = [bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += BIT.sum(x)
    BIT.add(x, 1)

print(ans)

Solution (Python):
from itertools import accumulate
import sys
sys.setrecursionlimit(10**8)
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):
        return self.search(j)-self.search(i-1)

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
B=list(accumulate([0]+A))
for i in range(N+1):
    B[i]-=K*i
C=sorted(set(B))
t=len(C)
D={ C[i]:i for i in range(t)}
tree=BIT(t)
ans=0
for i in range(N+1):
    ans+=tree.search(D[B[i]]+1)
    tree.add(D[B[i]]+1,1)
print(ans)

Solution (Python):
from itertools import accumulate
import sys
sys.setrecursionlimit(10**8)
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):
        return self.search(j)-self.search(i-1)

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
B=list(accumulate([0]+A))
for i in range(N+1):
    B[i]-=K*i
C=sorted((B[i],i) for i in range(N+1))
D=[-1]*(N+1)
D[C[0][1]]=0
s=C[0][0]
t=0
for i in range(1,N+1):
    if s<C[i][0]:
        s=C[i][0]
        t+=1
        D[C[i][1]]=t
    else:
        D[C[i][1]]=t
tree=BIT(t+1)
ans=0
for i in range(N+1):
    ans+=tree.search(D[i]+1)
    tree.add(D[i]+1,1)
print(ans)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    n, k = f.read_int_list()
    a = [f.read_int() for _ in xrange(n)]

    s = [0] * (n+1)
    for i in xrange(n):
        s[i+1] = s[i] + a[i] - k

    ss = compress(s)

    ans = 0
    bit = BinaryIndexedTree(n+1)
    for si in ss:
        ans += bit.sum(si+1)
        bit.add(si+1, 1)

    return ans


def compress(ary):
    d = dict(zip(sorted(set(ary)), range(len(ary))))
    return [d[item] for item in ary]


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in range(size + 1)]
        self.size = size

    def sum(self, i):
        """sum 1 to i"""
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """add x to bit[i]"""
        while i <= self.size:
            self.bit[i] += x
            i += i & -i


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

class BIT:
  def __init__(self, n):
    self._size = n
    self._body = [0] * (n+1)
  def __repr__(self):
    return ("BIT([" + ", ".join(str(x) for x in self._body) + "])")
  def size(self):
    return self._size
  def add(self, i, v):
    assert 0 <= i < self.size()
    i += 1
    while(i <= self.size()):
      self._body[i] += v
      i += i & -i
  def sum(self, *args):
    assert 1 <= len(args) <= 2
    if len(args) == 1: 
      i = args[0]
      assert 0 <= i <= self.size()
      s = 0
      while(i > 0):
        s += self._body[i]
        i -= i & -i
      return s
    else: 
      (i, j) = args
      return self.sum(j) - self.sum(i)

N, K = reads()
A = []
for _ in range(N):
  a = read()
  A.append(a-K)

psum = [0] + list(accumulate(A))

inv = sorted(set(psum))
L = len(inv)
invd = {inv[i]: i for i in range(L)}
bt = BIT(L)

ans = 0
for s in psum:
  c = invd[s]
  ans += bt.sum(c+1)
  bt.add(c, 1)
print(ans)

Solution (Python):
N,K = map(int,input().split())
src = [int(input()) for i in range(N)]

cums = [(0,1)]
for i,a in enumerate(src):
    cums.append((cums[-1][0] + a - K, i+2))

bit = [0] * (N+2)
def bit_add(a,w):
    x = a
    while x <= N:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

ans = 0
for i,a in sorted(cums):
    ans += bit_sum(a-1)
    bit_add(a, 1)
print(ans)

Solution (Python):

class BIT(object):

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

    def put(self, i):
        while(i<=self.n):
            self.lst[i]+=1
            i+=(i&-i)

    def get(self, i):
        ret=0
        while(i!=0):
            ret+=self.lst[i]
            i-=(i&-i)
        return ret

if __name__ == '__main__':
    ipt=input().split(' ')
    n=int(ipt[0])
    k=int(ipt[1])
    a=[(0,1)]
    for i in range(n):
        a.append((a[-1][0]+int(input())-k, i+2))
    a.sort()
    bit=BIT(n+1)
    ret=0
    for e in a:
        ret+=bit.get(e[1])
        bit.put(e[1])
    print(ret)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n,k = LI()
    a = [I() for _ in range(n)]

    b = [0]
    for i in range(n):
        b.append(b[-1] + a[i] - k)

    d = {}
    for c,i in zip(sorted(set(b)), range(n+1)):
        d[c] = i
    e = [d[c] for c in b]

    l = len(d)

    def f(a,b):
        return a+b

    seg = Seg(l, 0, f)
    for c in e:
        seg.update(c, seg.find(c) + 1)

    r = 0
    for c in e[::-1]:
        t = seg.query(0,c+1)
        r += t-1
        seg.update(c, seg.find(c) - 1)

    return r

print(main())

Solution (Python):
N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+2)

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

Solution (Python):
N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+3)

def sumation(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 += sumation(i+1)
    add(i+1, 1)
    
print(ans)

Solution (Python):
N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+5)

def sumation(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 += sumation(i+1)
    add(i+1, 1)
    
print(ans)