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):
"""
sum{j} - sum(i) >= K(j - i)
sum{j} - Ki >= sum(i) - Ki
"""

n,k = map(int,input().split())

al = []

for _ in range(n):
    a = int(input())
    al.append(a)

import itertools
al_ac = [0] + list(itertools.accumulate(al))

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



def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}

dic = compress(al_ac)
bl = [dic[b] for b in al_ac]
k = max(bl)


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)


ans = 0
bit = BIT(k+2)
for b in bl:
    ans += bit.sum(b+1)
    bit.add(b+1, 1)

print(ans)

Solution (Python):


from collections import deque
def f(L, R): return L + R 
def g(old, new): return old+new 
zero = 0 

class segtree:
    def __init__(self, N, z): 
        self.M = 1
        while self.M<N: self.M *= 2
        self.dat = [z] * (self.M*2-1)
        self.ZERO = z

    def update(self, x, idx, l=0, r=-1):
        if r==-1: r = self.M
        idx += self.M-1
        self.dat[idx] = g(self.dat[idx], x)
        while idx > 0:
            idx = (idx-1)//2
            self.dat[idx] = f(self.dat[idx*2+1], self.dat[idx*2+2])

    def query(self, a, b=-1, idx=0, l=0, r=-1):
        if r==-1: r = self.M
        if b==-1: b = self.M
        q = deque([])
        q.append([l, r, 0])
        ret = self.ZERO
        while len(q):
            tmp = q.popleft()
            L = tmp[0]
            R = tmp[1]
            if R<=a or b<=L: continue
            elif a<=L and R<=b:
                ret = f(ret, self.dat[tmp[2]])
            else:
                q.append([L, (L+R)//2, tmp[2]*2+1])
                q.append([(L+R)//2, R, tmp[2]*2+2])
        return ret



def zaatu(LIST):
    s = set(LIST)
    ar = list(s)
    ar.sort()
    dic = dict()
    for i in range(len(ar)): dic[ar[i]] = i
    return dic

n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
for i in range(n):
    a[i] -= k
    if i!=0: a[i] += a[i-1]
dic = zaatu(a)
seg = segtree(n+1, 0)
ans = 0
for num in a: ans += (num>=0)
for i in range(n): a[i] = dic[a[i]]
for i in range(n):
    ans += seg.query(0, a[i]+1)
    seg.update(1, a[i])
print(ans)

Solution (Python):
from itertools import accumulate
from collections import Counter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N + 1
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

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

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


def coordinate_Compression_1D(A):
    
    B = sorted(list(set(A)))
    idx = {a: i for i, a in enumerate(B, start=1)}
    return [idx[a] for a in A]


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    Aacc = list(accumulate([0] + A))
    B = [a - K * i for i, a in enumerate(Aacc)]
    Bcmp = coordinate_Compression_1D(B)

    bit = BinaryIndexTree(N+10)
    ans = 0
    for i, b in enumerate(Bcmp):
        ans += bit.sum(b)
        bit.add(b, 1)
    print(ans)

Solution (Python):





def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c


root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

import random

def small(val):
    global root
    x=root
    ans=0
    while x:
        if x[2]>val:
            x=x[0]
        elif x[2]<val:
            if x[0]:
                ans+=x[0][4]+1
            else:
                ans+=1
            x=x[1]
    return ans

import random,sys

input=sys.stdin.readline

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

for i in range(1,N):
    A[i]+=A[i-1]

A=[0]+A
A=[(A[i],i) for i in range(0,N+1)]
A.sort()
A=[A[i][1] for i in range(0,N+1)]
ans=0
for i in range(0,N+1):
    ans+=small(A[i])
    insert(A[i],random.randint(0,100000))

print(ans)

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

for i in range(N):
    A[i]-=K

from itertools import accumulate
S=[0]+list(accumulate(A))

SORTED_S=sorted(set(S)|{-1<<63})
compression_dict={a: ind for ind, a in enumerate(SORTED_S)}

LEN=len(compression_dict)

BIT=[0]*(LEN+1) 

def update(v,w): 
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) 

def getvalue(v): 
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) 
    return ANS

ANS=0
for i in range(N+1):
    ANS+=getvalue(compression_dict[S[i]])
    update(compression_dict[S[i]],1)

print(ANS)

Solution (Python):
from bisect import bisect_left, bisect_right

class Set(): 
    def __init__(self, valuelist, INF=10**18+1):
        self.n = len(valuelist) + 1
        self.value = sorted(valuelist) + [INF]
        self.comp = {v : k for k, v in enumerate(self.value, 1)}
        self.bit = BinaryIndexedTree(self.n)

    def insert(self, x, k=1):
        self.bit.add(self.comp[x], k)

    def delete(self, x, k=1):
        self.bit.add(self.comp[x], -k)

    def count(self, x):
        return self.bit.get(self.comp[x])

    def sum(self, x):
        return self.bit.sum(self.comp[x])

    def get(self, k): 
        return self.value[self.bit.bisect_left(k) - 1]

class BinaryIndexedTree(): 
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def get(self, index):
        return self.sum(index) - self.sum(index - 1)

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        if res >= self.n:
            return self.n
        return res + 1

import sys
input = sys.stdin.readline

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

cum = [0]

for i in range(N):
    cum.append(cum[-1] + A[i])

V = [cum[i] - K * i for i in range(N + 1)]

S = Set(V)

res = 0

for i in range(N + 1):
    res += S.sum(V[i])
    S.insert(V[i])

print(res)

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 compress(arr):
    a = sorted([(v,k) for k,v in enumerate(arr)])
    return [k+1 for v,k in a]

n,k = map(int, input().split())
a = [int(input())-k for i in range(n)]
cumsum = [0] + list(accumulate(a))
comp = compress(cumsum)
bit = BIT(n+1)
ans = n * (n+1) // 2
for k,v in enumerate(comp):
  bit.add(v,1)
  ans -= k+1-bit.sum(v)
print(ans)

Solution (Python):
class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def query(self, l, r):
        res = self.element
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = self.func(res, self.seg[r-1])
            if l & 1:
                res = self.func(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

import sys
input = sys.stdin.readline
read = sys.stdin.read
from itertools import accumulate

def compress(arr):
    *XS, = set(arr)
    XS.sort()
    d = {e: i for i, e in enumerate(XS)}
    return [d[e] for e in arr]

n, k = map(int, input().split())
if n == 1:
  print(int(int(input()) >= k))
  exit()
A = list(map(lambda x:int(x)-k, read().split()))
L = [0] + list(accumulate(A))
L = compress(L)
seg = Segtree([0]*(max(L)+1), lambda x, y:x+y, 0)
ans = 0
for l in L:
  ans += seg.query(0, l+1)
  t = seg.get(l)
  seg.update(l, t+1)
print(ans)

Solution (Python):
class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def query(self, l, r):
        res = self.element
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = self.func(res, self.seg[r-1])
            if l & 1:
                res = self.func(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

import sys
input = sys.stdin.readline
read = sys.stdin.read
from itertools import accumulate

def compress(arr):
    *XS, = set(arr)
    XS.sort()
    d = {e: i for i, e in enumerate(XS)}
    return [d[e] for e in arr]

n, k = map(int, input().split())
if n == 1:
  print(int(int(input()) >= k))
  exit()
A = list(map(lambda x:int(x)-k, read().split()))
L = [0] + list(accumulate(A))
L = compress(L)
seg = Segtree([0]*(max(L)+1), lambda x, y:x+y, 0)
ans = 0
for l in L:
  ans += seg.query(0, l+1)
  t = seg.get(l)
  seg.update(l, t+1)
print(ans)

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

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

tmp = sorted(B)

dic = dict()
for index, x in enumerate(tmp):
    dic[x] = index


N = len(B)
bit = [0] * (N + 1)
def total(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
    return

ans = 0
for b in B:
    
    n = dic[b]
    ans += total(n + 1)
    
    
    add(n + 1, 1)

print (ans)

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

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

tmp = sorted(B)

dic = dict()
for index, x in enumerate(tmp):
    dic[x] = index


N = len(B)
bit = [0] * (N + 1)
def total(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
    return

ans = 0
for b in B:
    
    n = dic[b]
    ans += total(n + 1)
    
    
    add(n + 1, 1)

print (ans)

Solution (Python):



def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]





class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a

n,k=map(int,input().split())
a=[int(input())-k for _ in range(n)]
b=[0]
for i in a:b.append(b[-1]+i)
b=position_zip(b,0)
bit=BinaryIndexedTree(n+1)
ans=0
for i in b:
  ans+=bit.sum(0,i)
  bit.add(i,1)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






from operator import itemgetter
def compress(A,reduction=True,start=0):
    if reduction:
        d = {}
        A_sort = sorted(list(set(A)))
        for i,a in enumerate(A_sort):
            d[a] = i+start
        return [d[a] for a in A]
    else:
        A_sort = sorted(enumerate(A),key=itemgetter(1,0))
        A_compress = [0]*len(A)
        for i,(j,_) in enumerate(A_sort):
            A_compress[j] = i+start
        return A_compress

class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1


N,K = LI()
a = LIR(N,1)
a = list(map(lambda x: x-K, a))
ca = [0]
for i in range(N):
    ca.append(ca[-1]+a[i])

A = compress(ca,start=1)
bit = BIT(max(A))

ans = 0
for i in range(N+1):
    ans += bit.sum(A[i])
    bit.add(A[i],1)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
 
def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    
    def acc(self, i):
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

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

for i in range(N):
    acc += a[i]
    l.append(acc-K*(i+1))

idx = compress(l)
bit = BIT(len(list(idx.keys())))
bit.add(idx[0], 1)
ans = 0
acc = 0

for i in range(N):
    acc += a[i]
    ans += bit.acc(idx[acc-K*(i+1)])
    bit.add(idx[acc-K*(i+1)], 1)
    
print(ans)

Solution (Python):
import bisect

def segfunc(x,y):
    return x+y

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,k=map(int,input().split())
num=2**(n).bit_length()
seg=[ide_ele]*2*num
a=[]
for i in range(n):
    p=int(input())
    a.append(p-k)
d=[0]
for i in range(n):
    d.append(d[-1]+a[i])
b=sorted(d)
a=[]
for i in d:
    p=bisect.bisect_left(b,i)
    a.append(p)

ans=0
a.reverse()
update(a[0],1)
for i in range(n):
    ans+=query(a[i+1],1+n)
    update(a[i+1],query(a[i+1],a[i+1]+1)+1)
print(ans)


exit()

Solution (Python):
from itertools import accumulate as acc

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

def bit_add(ls, i, n):
  i += 1
  while i<len(ls):
    ls[i] += n
    i += i & -i

N, K, *A = map(int, open(0).read().split())
A = [a-K for a in A]
B = [(b,i) for i, b in enumerate(acc(A))]
bit_B = [0]*(N+1)
B.sort(reverse=True)
ans = sum(c[0]>=0 for c in B)
for b,i in B:
  bit_add(bit_B,i,1)
  ans += bit_sum(bit_B,N-1)-bit_sum(bit_B,i)
print(ans)

Solution (Python):
from itertools import accumulate as acc
class BIT:
  def __init__(self, n):
    self.N = n+1
    self.bit = [0]*self.N
  
  def bit_sum(self, i):
    s = 0
    i += 1
    while i>0:
      s += self.bit[i]
      i -= i & -i
    return s

  def bit_add(self, i, n):
    i += 1
    while i<self.N:
      self.bit[i] += n
      i += i & -i

N, K, *A = map(int, open(0).read().split())
A = [a-K for a in A]
B = [(b,i) for i, b in enumerate(acc(A))]
bit_B = BIT(N)
B.sort(reverse=True)
ans = sum(c[0]>=0 for c in B)
for b,i in B:
  bit_B.bit_add(i,1)
  ans += bit_B.bit_sum(N-1)-bit_B.bit_sum(i)
print(ans)

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
import collections
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


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


class SegmentTree:
    """
    各ノードが半開区間に対応した完全二分木。
    子は親を半分にした区間を持つ。
    構築O(n), 区間に対する操作O(logn), 値の更新O(logn)
    区間に対する操作は最小値, 最大値, 区間に対する和など柔軟に変更して用いよう！
    """

    def __init__(self, x, init_val):  
        self.init_val = init_val
        self.length = 2 ** ((len(x) - 1).bit_length())
        self.data = [init_val] * (2 + 1) * self.length
        for i in range(len(x)):
            self.data[i + self.length - 1] = x[i]
        for i in range(self.length - 2, -1, -1):
            self.data[i] = func(self.data[2 * i + 1], self.data[2 * i + 2])

    def teach_current_val(self, index):
        return self.data[index + self.length - 1]

    def replace(self, index, val):  
        index += self.length - 1
        self.data[index] = val
        while index:
            index = (index - 1) // 2
            self.data[index] = func(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):  
        if right <= left:
            return self.init_val
        left += self.length - 1  
        right += self.length - 2  
        ans = self.init_val
        while right > left + 1:
            if left & 1 == 0:  
                ans = func(ans, self.data[left])
            if right & 1 == 1:  
                ans = func(ans, self.data[right])
                right -= 1
            left //= 2
            right = (right - 1) // 2
        if left == right:
            ans = func(ans, self.data[left])
        else:
            ans = func(func(ans, self.data[left]), self.data[right])
        return ans


N, K = map(int, input().split())
a = [0] * (N + 1)
for i in range(N):
    a[i + 1] = int(input()) - K
a = list(itertools.accumulate(a))
cc = sorted(list(dict.fromkeys(a)))
c = collections.Counter(a)
for i in range(len(a)):
    if type(c[a[i]]) == int:
        c[a[i]] = [i]
    else:
        c[a[i]].append(i)
seg = SegmentTree([0] * (N + 1), 0)
ans = 0
for i in cc:
    for l in c[i]:
        ans += seg.query(0, l)
        seg.replace(l, 1)
print(ans)

Solution (Python):
bit = [0 for _ in range(252525)]

def get(r):
    r += 1

    res = 0
    while r > 0:
        res += bit[r]
        r -= r & -r
    
    return res

def update(k, x):
    k += 1

    while k < 252525:
        bit[k] += x
        k += k & -k
    
    return

n, k = map(int, input().split())

a = [int(input()) for _ in range(n)]

v = [0]

for i in range(n):
    v.append(v[i] + a[i])

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

st = sorted(list(set(v)))
mp = {t:i for i, t in enumerate(st)}

ans = 0

for i in range(n + 1):
    ans += get(mp[v[i]])
    update(mp[v[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+=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):
    return self._sum(j)-self._sum(i)
n,k=map(int,input().split())
a=[int(input()) for i 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]-=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):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = [0] * N
for i in range(N): a[i] = int(input())
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

table = [0] * (N + 1)
for i in range(1, N + 1): table[i] = cs[i] - i * K

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)

fwk = BIT(N + 1)

def compress(init_val):
  t = sorted(set(init_val))
  d = dict([[t[i], i] for i in range(len(t))])
  res = [0] * len(init_val)
  for i in range(len(init_val)): res[i] = d[init_val[i]]
  return res

comtable = compress(table)

for i in range(N + 1): fwk.add(comtable[i] + 1, 1)

res = 0
for i in range(N):
  fwk.add(comtable[i] + 1, -1)
  res += fwk.get(comtable[i], N + 1)
print(res)

Solution (Python):
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

from itertools import accumulate
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = [int(input())-k for i in range(n)]
acc = [0]+list(accumulate(a))
acc_i = []
for i,x in enumerate(acc):
  acc_i.append((x,i+1))
acc_i.sort()
bit = Bit(n+2)
ans = 0
for i in range(n+1):
  x = acc_i[i][1]
  ans += n+1-x+bit.sum(x)
  bit.add(1,-1)
  bit.add(x+1,1)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

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

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


n, k = LI()
A = IR(n)
A = [a - k for a in A]
A = [0] + list(accumulate(A))
D = {}
for i, v in enumerate(sorted(set(A))):
    D[v] = i

for i in range(n + 1):
    A[i] = D[A[i]]

bit = BIT(max(A) + 1)
c = 0
for a in A:
    c += bit.sum(a)
    bit.add(a, 1)


print(c)

Solution (Python):

def bitadd(a,w,bit): 

    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)

def bitsum(a,bit): 

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


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

a = []

for i in range(N):

    A = int(input())
    a.append(A-K)


B = [0]

for i in range(N):

    B.append(B[-1] + a[i])


C = B.copy()
C.sort()

dic = {}

num = 1
for i in range(N+1):

    if i == 0:
        dic[C[i]] = num
        num += 1
    elif C[i] != C[i-1]:
        dic[C[i]] = num
        num += 1

for i in range(N+1):
    B[i] = dic[B[i]]

BIT = [0] * (len(B) + 1)

ans = 0

for i in range(N+1):

    ans += bitsum(B[i],BIT)
    bitadd(B[i],1,BIT)

print (ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()

class BIT(object):
    def __init__(self,A,dot=lambda x,y:x+y,e=0,inv=None):
        n=len(A)
        self.__n=n; self.__dot=dot; self.__e=e; self.__inv=inv; self.__node=['$']+A
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r),self.sum(l))

def resolve():
    n,k=map(int,input().split())
    A=[int(input())-k for i in range(n)]
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]

    
    D={s:i for i,s in enumerate(sorted(set(S)))}
    for i in range(n+1):
        S[i]=D[S[i]]

    ans=0
    bit=BIT([0]*(max(S)+1))
    for s in S:
        ans+=bit.sum(s+1)
        bit.add(s)

    print(ans)
resolve()