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



Sample input:
3 6
7
5
7


Sample output:
5

Submission status: Accepted

Solution code:
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 sum
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys,bisect,math
input = sys.stdin.readline

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
# i と x が与えられたとき ai += x とする ( O(log n) )
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[j+1]-b[i]:a[i]~a[j]
b = [0]
for i in range(n):
    b.append(b[-1]+a[i])

#c[i]:b[i]-k*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])
    #bitsum(bit,a[j]): j-1番目までの中でa[j]以下のもの
    bit = bitadd(bit,c[j],1)


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

# BIT
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        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)

Submission status: Accepted

Solution code:
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):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        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)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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 #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
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: # [0, i)の和をとる
      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)の和をとる
      (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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

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

from itertools import accumulate,repeat

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

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

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

result = 0
bit = BinaryIndexedTree(N+1)

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

print(result)

Submission status: Accepted

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

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

from bisect import bisect

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

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

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

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

result = 0
bit = BinaryIndexedTree(N+1)

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

print(result)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

inf = 1<<60
ans = 0

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

    MergeSort(s)

    print(ans)

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

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

    res = merge(apre, asuf)

    return res

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

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

    la = 0
    lb = 0

    res = []

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

    return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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

    # 座標圧縮
    s = [(si, i) for (i, si) in enumerate(s)]
    s.sort()

    z = [None] * (n + 1)

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

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

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

    # FenwickTreeで転倒数を数える
    ft = FenwickTree(num + 1)

    ans = 0

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

    print(ans)

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

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

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

    def psum(self, r):
        res = 0

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

        return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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