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):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

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

def main():
    n,k=MI()
    aa=np.zeros(n+1,dtype="i8")
    aa[0]=k
    for i in range(1,n+1):
        aa[i]=II()
    aa-=k
    cs=np.cumsum(aa)
    
    
    
    ss=set()
    for s in cs:
        ss.add(s)
    enc={s:i for i,s in enumerate(sorted(ss))}
    
    
    bit=BitSum(len(ss))
    ans=0
    for s in cs:
        enc_s=enc[s]
        ans+=bit.sum(enc_s)
        bit.update(enc_s,1)
    print(ans)

main()

Solution (Python):




class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

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

    def add(self, i, x):
        
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


def main():
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = (int(input()) - K for _ in range(N))

    acc = (0,) + tuple(accumulate(A))

    def compress(iter):
        convert = {x: i for i, x in enumerate(sorted(iter), start=1)}
        
        
        return (convert[x] for x in iter)

    comacc = compress(acc)

    ret = 0

    b = BIT(N + 1)
    for x in comacc:
        ret += b.sum(x)
        b.add(x, 1)

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):




class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

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

    def add(self, i, x):
        
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


def main():
    from itertools import accumulate

    N, K = map(int, input().split())
    A = (int(input()) - K for _ in range(N))

    acc = (0,) + tuple(accumulate(A))

    def compress(iter):
        convert = {x: i for i, x in enumerate(sorted(iter), start=1)}
        
        
        return (convert[x] for x in iter)

    comacc = tuple(compress(acc))

    ret = 0

    b = BIT(len(comacc))
    for x in comacc:
        ret += b.sum(x)
        b.add(x, 1)

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from sys import stdin
    input=stdin.readline
    from itertools import accumulate as ac

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

    
    bit = [0]*(n+2)

    
    def add(a, w):
        x = a
        while x < n+2:
            
            bit[x] += w
            x += x & (-x)

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

    aca = [0]+list(ac(a))
    aca = sorted([(i, j) for i, j in enumerate(aca)],
                 key=lambda x: -x[1])+[(0, 10**20)]
    temp = []
    temp2 = [aca[0][0]]
    for i in range(1, n+2):
        if aca[i][1] == aca[i-1][1]:
            temp2.append(aca[i][0])
        else:
            temp.append(temp2)
            temp2 = [aca[i][0]]
    ans = 0
    for temp2 in temp:
        l=len(temp2)
        ans += l*(l-1)//2
        for i in temp2:
            ans += sum_(n+1)-sum_(i)
        for i in temp2:
            add(i+1, 1)
    print(ans)


main()

Solution (Python):
from bisect import bisect_left

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

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

t = list(set(s))
t.sort()
for i in range(N + 1) :
    s[i] = bisect_left(t, s[i])

class BinaryIndexedTree() :
    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
            
ret = 0
BIT = BinaryIndexedTree(N + 5)
for i in range(N + 1) :
    ret += BIT.sum(s[i] + 1)
    BIT.add(s[i] + 1, 1)
    
print(ret)

Solution (Python):

class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    
    
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

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

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    
    
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()


import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
ans = 0
B = []
b = 0
for a in A:
    b += a-K
    B.append(b)
    if b >= 0:
        ans += 1

ind_to_co = [0] + sorted(B)
co_to_ind = {}
for i in range(N):
    co_to_ind[ind_to_co[i+1]] = i+1

bit = BITbisect(N)
for b in B:
    bit.insert(co_to_ind[b])

for b in B:
    ib = co_to_ind[b]
    bit.delete(ib)
    ans += bit.length() - bit.bisect_left(ib)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

acca = []

def merge(n, l, m, r):
    global acca
    cnt = 0
    n1, n2 = m - l, r - m
    la, ra = [], []
    for i in range(n1):
        la.append(acca[l + i])
    for i in range(n2):
        ra.append(acca[m + i])
    la.append(float("inf"))
    ra.append(float("inf"))
    i, j = 0, 0
    for k in range(l, r):
        if la[i] <= ra[j]:
            acca[k] = la[i]
            i += 1
        else:
            acca[k] = ra[j]
            j += 1
            cnt += n1 - i
    return cnt


def mergesort(n, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        c1 = mergesort(n, l, m)
        c2 = mergesort(n, m, r)
        c3 = merge(n, l, m, r)
        return c1 + c2 + c3
    else:
        return 0


def main():
    global acca
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    a = [_a - k for _a in a]
    acca = [0 for i in range(n + 1)]
    for i, _a in enumerate(a):
        acca[i + 1] = acca[i] + _a

    print(n * (n + 1) // 2 - mergesort(n + 1, 0, n + 1))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left
import sys
input = sys.stdin.readline


class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        lo = -1
        hi = self.N
        while lo < hi:
            mid = (lo+hi)//2
            if self.query(mid) < x:
                lo = mid + 1
            else:
                hi = mid
        return lo


def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    B = [0] * (N+1)
    for i in range(N):
        B[i+1] = B[i] + A[i] - K
    sortedB = sorted(B)
    C = [0] * (N+1)
    bit = BinaryIndexedTree(N+1)
    ans = 0
    for i in range(N+1):
        x = bisect_left(sortedB, B[i])
        C[i] = x
        ans += bit.query(x)
        bit.add(C[i], 1)
    print(ans)


if __name__ == "__main__":
    main()

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

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

    def add(self, i, v):
        while i <= self.n:
            self.data[i-1] += v
            i += i & -i

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

n,k = map(int, input().split())
a = [int(input())-k for i in range(n)]
s = [0]
for i in a:
    s.append(s[-1]+i)


d = {j:i for i,j in enumerate(sorted(set(s)))}
bit = BIT_RSQ(len(d))
ans = 0
for i in range(n):
    
    bit.add(d[s[i]]+1, 1)
    ans += bit.sum(d[s[i+1]]+1)
print(ans)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def compress(A):
    """ 座標圧縮 """

    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(set(A))):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

N, K = MAP()

A = [a-K for a in LIST(N)]


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

zipped, _ = compress(acc)

bit = BIT(len(zipped))
cnt = 0
for a in acc:
    
    cnt += bit.sum(zipped[a])
    bit.add(zipped[a], 1)
print(cnt)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

N, K = MAP()

A = [a-K for a in LIST(N)]


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

zip_acc = {}
for i, a in enumerate(sorted(set(acc))):
    zip_acc[a] = i

bit = BIT(len(zip_acc))
cnt = 0
for a in acc:
    
    cnt += bit.sum(zip_acc[a])
    bit.add(zip_acc[a], 1)
print(cnt)

Solution (Python):
n,k = map(int,input().split())
a = [0] + [int(input())-k for _ in range(n)]

for i in range(n):
  a[i+1] += a[i]
  
def comp(lis):
  dic = {x:i+1 for i,x in enumerate(sorted(list(set(lis))))}
  return list(map(lambda x:dic[x],lis))

a = comp(a)
 
class BIT:
    def __init__(self,n):
        self.n = n
        self.size = 1<<((n-1).bit_length())
        self.bit = [0]*(self.size+1)

    def bitsum(self,idx):
        tmp = 0
        while idx:
            tmp += self.bit[idx]
            idx -= idx & -idx
        return tmp

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

bit = BIT(max(a))
ans = 0
for x in a:
    ans += bit.bitsum(x)
    bit.bitadd(x,1)
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')


input=lambda: sys.stdin.readline().rstrip()

show_flg=False


class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)

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

    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return

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

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1


class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)

n,k=LI()
a=[0]
for _ in range(n):
    a.append(a[-1]+I()-k)

ans=0
show(a)
b=[(j,i) for i,j in enumerate(sorted(a[:]))]
d=dict(b)
b=[d[i] for i in a[:]]
show(b)

bt=Bit0(n+1)
for i in b:
    ans+=bt.sum(i+1)
    bt.add(i,1)

print(ans)

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

n, k = [int(item) for item in input().split()]
a = [0] 
for i in range(n):
    a.append(int(input()) - k)
for i in range(1, n+1):
    a[i] += a[i - 1]
a_set = sorted(list(set(a)))
comp = dict() 
for i, item in enumerate(a_set):
    comp[item] = i
for i, item in enumerate(a):
    a[i] = comp[item]

n = len(a_set) + 5
bit = [0] * (n + 1) 


def bit_add(x, w):
    while x <= n:
        bit[x] += w
        x += x & -x


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

ans = 0
for item in a:
    ans += bit_sum(item + 1)
    bit_add(item + 1, 1)
print(ans)

Solution (Python):
from itertools import accumulate

def main():
    N, K, *A = map(int, open(0).read().split())

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

    memo = {n: i for i, n in enumerate(sorted(set(B)), 1)}

    N += 1
    tree = [0] * (N + 1)

    def bit_sum(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def bit_add(i, x):
        while i <= N:
            tree[i] += x
            i += i & -i

    ans = 0
    for b in map(memo.get, B):
        ans += bit_sum(b)
        bit_add(b, 1)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

def main():
    class BIT:
        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, *A = map(int, open(0).read().split())

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

    memo = {n: i for i, n in enumerate(sorted(set(B)), 1)}
    bit = BIT(N + 1)

    ans = 0
    for b in map(memo.get, B):
        ans += bit.sum(b)
        bit.add(b, 1)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

class BIT:
    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

def main():
    N, K, *A = map(int, open(0).read().split())

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

    memo = {n: i for i, n in enumerate(sorted(set(B)), 1)}
    bit = BIT(N + 1)

    ans = 0
    for b in map(memo.get, B):
        ans += bit.sum(b)
        bit.add(b, 1)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

class BIT:
    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, *A = map(int, open(0).read().split())

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

memo = {n: i for i, n in enumerate(sorted(set(B)), 1)}
bit = BIT(N + 1)

ans = 0
for b in map(memo.get, B):
    ans += bit.sum(b)
    bit.add(b, 1)

print(ans)

Solution (Python):
n,k=map(int,input().split())
b=[0]*(n+1)
for i in range(n):
    b[i+1]=b[i]+int(input())-k
a=sorted(set(b))
s={a[i-1]:i for i in range(1,len(a)+1)}
c=[]
for i in b:
    c.append(s[i])
b=[0]*(len(a)+1)
def f(x):
    c=0
    while x>0:
        c+=b[x]
        x-=x&-x
    return c
def g(x):
    while x<len(a)+1:
        b[x]+=1
        x+=x&-x
e=0
for i in range(n+1):
    e+=f(c[i])
    g(c[i])
print(e)

Solution (Python):
from bisect import bisect_left

class SegmentTree:
    def __init__(self, N):
        self.N = 2 * pow(2, N.bit_length()) - 1
        self.data = [0 for _ in range(2*self.N)]
    
    def update(self, k, x):
        k += self.N-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = sum([self.data[2*k+1], self.data[2*k+2]])
    
    
    def query(self, l, r):
        L = l + self.N
        R = r + self.N
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = sum([s, self.data[R-1]])
            if L & 1:
                s = sum([s, self. data[L-1]])
                L += 1
            L >>= 1; R >>= 1
        return s

    def node(self, k):
        return st.query(k, k+1)

def compress(arr):
    N = len(arr)
    narr = sorted(arr)
    pressed = [-1] * N
    for i in range(N):
        pressed[i] = bisect_left(narr, arr[i])
    return pressed
    

def accmulate(arr):
    N = len(arr)
    cs = [0]*(N+1)
    for i in range(N):
        cs[i+1] = cs[i] + arr[i]
    return cs


def query(cs, l, r):
    return cs[r] - cs[l]

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

cs = accmulate(A)
cs = compress(cs)
st = SegmentTree(N)

ans = 0

for i in range(N+1):
    ans += st.query(0, cs[i] + 1)
    st.update(cs[i], st.node(cs[i]) + 1)

print(ans)

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


class Bit:
    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


def main():
    N, K = map(int, input().split())
    ac = [0] * (N + 1)
    place = {0: 0}
    for i in range(N):
        a = int(input()) - K
        ac[i+1] = ac[i] + a * (10 ** 5) + 1
        place[ac[i+1]] = i+1
    ac.sort()
    ac_cmpr = [0] * (N+1)
    for i in range(N+1):
        ac_cmpr[place[ac[i]]] = i + 1
    bit = Bit(N+2)
    bit.add(ac_cmpr[0], 1)
    ans = 0
    for i in range(1, N+1):
        ans += bit.sum(ac_cmpr[i])
        bit.add(ac_cmpr[i], 1)

    print(ans)


if __name__=='__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate

import numpy as np


class Bit:
    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())
aaa = [0] + list(map(int, sys.stdin))
acc = [a - i * k for i, a in enumerate(accumulate(aaa))]
values = sorted(set(acc))
dct = {v: i for i, v in enumerate(values, start=1)}
bit = Bit(len(values))
ans = 0
for d in acc:
    i = dct[d]
    ans += bit.sum(i)
    bit.add(i, 1)
print(ans)

Solution (Python):
import sys

import numpy as np


class Bit:
    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())
aaa = np.fromiter(sys.stdin, dtype=np.int64)
aaa = np.insert(aaa, 0, 0)
acc = np.add.accumulate(aaa) - np.arange(0, k * n + 1, k)
dct = {v: i for i, v in enumerate(np.unique(acc), start=1)}
bit = Bit(len(dct))
ans = 0
for d in acc:
    i = dct[d]
    ans += bit.sum(i)
    bit.add(i, 1)
print(ans)

Solution (Python):
n,k=map(int,input().split())
A=[]
for i in range(n):
  A.append(int(input())-k)
AA,BB=[0]*(n+1),[0]*(n+1)
AA[-2]=A[-1]
BB[-2]=A[-1]
for i in reversed(range(n-1)):
  AA[i]=AA[i+1]+A[i]
  BB[i]=BB[i+1]+A[i]
BB.sort()
cur=1
D=dict()
D[BB[0]]=cur
for i in range(1,n+1):
  if BB[i]==BB[i-1]:
    continue
  else:
    cur+=1
    D[BB[i]]=cur
AAA=[0]*(n+1)
for i in range(n+1):
  AAA[i]=D[AA[i]]

nn=18
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

ans=0
for i in range(n+1):
  ans+=i-bitsum(BIT,AAA[i]-1)
  bitadd(BIT,AAA[i],1)
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()

    return


def B():
    n = I()

    return


def C():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n,k = LI()
    a = IR(n)
    a.insert(0,0)
    for i in range(n+1):
        a[i] -= k
    for i in range(n):
        a[i+1] += a[i]
    b = list(set([a[i] for i in range(n+1)]))
    b.sort()
    for i in range(n+1):
        a[i] = bisect.bisect_right(b,a[i])
    bit = [0]*(max(a)+1)
    ans = 0
    for i in range(n+1):
        ans += sum(a[i])
        add(a[i])
    print(ans)
    return


def D():
    n = I()

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
N, K = map(int, input().split())
a = [int(input()) - K for _ in range(N)]
b = [0]+list(accumulate(a))
b_sorted = sorted(b)
b = [bisect_right(b_sorted, bi) for bi in b]
bit = BIT(N+1)
ans = 0
for i in range(N+1):
    ans += bit.sum(b[i])
    bit.add(b[i], 1)
print(ans)

Solution (Python):
import numpy as np

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

S = [(0, 0)]
ss = 0
for i in range(N):
  ss += (A[i] - K)
  S.append((ss, i+1))

S = sorted(S)


class Bit:
    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


bit = Bit(N+1)

ans = 0
for s,i in S:
  ans += bit.sum(i+1)
  bit.add(i+1, 1)
  
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate

N,K = map(int,input().split())
A = [int(input()) - K for _ in range(N)]
Acum = [0] + list(accumulate(A))

a_to_i = {a:i for i,a in enumerate(sorted(set(Acum)), 1)}

B = [a_to_i[a] for a in Acum]

L = len(a_to_i) + 1
tree = [0] * (L+1)


def BIT_update(tree, x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree, x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

answer = 0
for b in B:
    answer += BIT_sum(tree,b)
    BIT_update(tree,b)

print(answer)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


N, K = list(map(int, sys.stdin.readline().split()))
A = [int(sys.stdin.readline()) for _ in range(N)]


N += 1

D = list(itertools.accumulate([0] + [a - K for a in A]))


def compress(arr):
    """
    :param list of int arr:
    :return:
    """
    ret = [0] * len(arr)
    rank = 0
    prev = None
    for a, i in sorted([(a, i) for i, a in enumerate(arr)]):
        if a != prev:
            rank += 1
        ret[i] = rank
    return ret


def count(arr):
    """
    転倒数の逆。arr[L-1] <= arr[r] となる (L, r) の組み合わせ数
    :param list of int arr:
    :return:
    """
    ranks = compress(arr)
    bit = BinaryIndexedTree(size=max(ranks) + 1)
    ret = 0
    for i, rank in enumerate(ranks):
        ret += bit.sum(rank)
        bit.add(rank, 1)
    return ret


print(count(D))

Solution (Python):
import bisect
from itertools import accumulate

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, K = map(int, input().split())
    L = [int(input()) for _ in range(N)]

    L_acc = [0]+list(accumulate(L))
    for i in range(N+1):
        L_acc[i] -= (i)*K

    L_sort = list(sorted(set(L_acc)))
    L_comp = [-1]*(N+1)
    for i in range(N+1):
        key = L_acc[i]
        ind = bisect.bisect_left(L_sort, key)
        L_comp[i] = ind
    
    bit = [0]*(N+1)

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

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

    ans = 0
    for i, l in enumerate(L_comp):
        if l == 0:
            ans += N-i
            continue
        ans += sum_bit(l)
        add(l, 1)
    print(ans)


solve()