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:
n, k = map(int, raw_input().split())
A = [int(raw_input())-k for i in xrange(n)]
su = 0
v = [(0, 0)]
for i in xrange(n):
    su += A[i]
    v.append((su, i+1))
v.sort()

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

Submission status: Runtime Error

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a + b

	# k番目の値にxを加算
	def add(self, k, x):
		k += self.N0 - 1
		self.data[k] += x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N, K = getlist()
	A = []
	for i in range(N):
		a = int(input())
		A.append(a)

	# K引く
	for i in range(N):
		A[i] -= K
	
	# 累積和
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])

	# 座圧
	C = list(set(B))
	C.sort()
	D = defaultdict(int)
	for i in range(len(C)):
		D[C[i]] = i

	# 座標変換
	for i in range(N + 1):
		B[i] = D[B[i]]

	# セグ木
	ans = 0
	Seg = SegmentTree(N)
	for i in range(N + 1):
		b = B[i]
		val = Seg.query(0, b)
		ans += val
		Seg.add(b, 1)

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=[0]+[int(input())-k for _ in range(n)]
ac=np.cumsum(a)
##BITは分からない
def rec(l):
    ll=len(l)
    if ll<=1:
        return 0
    l1=l[:ll//2]
    l2=l[ll//2:]
    res=rec(l1)+rec(l2)
    l1.sort()
    l2.sort()
    i2=0
    for i in range(len(l1)):
        while i2<len(l2) and l2[i2]<l1[i]:
            res+=len(l1)-i
            i2+=1
    return res
print(n*(n+1)//2-rec(ac))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

class BIT:
    def __init__(self,n,default = 0):
        self.s = [default]*(n+1)
    
    def add(self,val,idx):
        while idx < n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx&(-idx)
        return
    
    def get(self,idx):
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx&(-idx)
        return res


n,k = map(int,input().split())
ans = 0
s = [0]*(n+1)
array = {0}
for i in range(n):
    s[i+1] = s[i] + int(input()) - k
    array.add(s[i+1])
array = sorted(array)
d = {x:i for i,x in enumerate(array)}
bit = BIT(len(array))
for t in s:
    ans += bit.get(d[t]+1)
    bit.add(1,d[t]+1)
print(ans)

Submission status: Runtime Error

Solution code:
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():
    import sys
    read = sys.stdin.read
    N, K = (int(i) for i in input().split())
    A = [int(s) for s in read().rstrip().split('\n')]
    from itertools import accumulate
    S = list(accumulate([0] + A))
    B = [s - K*i for i, s in enumerate(S)]
    c = {b: i+1 for i, b in enumerate(sorted(set(B)))}
    f = Bit(N)
    ans = 0
    for j in range(N+1):
        ans += f.sum(c[B[j]])
        f.add(c[B[j]], 1)
    print(ans)


if __name__ == '__main__':
    main()