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:
def examC():
    N = I()
    S = [I() for _ in range(N)]
    S1 = []
    for s in S:
        if s%10==0:
            continue
        S1.append(s)
    if S1==[]:
        print(0)
        return
    S1.sort()
    ans = sum(S)
    if ans%10==0:
        ans -= S1[0]
    print(ans)
    return

def examD():
    N, A, B = LI()
    H = [I() for _ in range(N)]
    H.sort()
    l = 0; r = (H[-1]-1)//B + 1
    while(r-l>1):
        now = (l+r)//2
        cur = 0
        for i in H:
            if i-now*B>0:
                cur += ((i-now*B-1)//(A-B) +1)
        if cur>now:
            l = now
        else:
            r = now
    ans = r
    print(ans)
    return

def examE():
    # 0許容(i += 1)
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

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

        def add(self, i, x=1):
            i += 1
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考　よくわかってない
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

        def inversion(self, A=[3, 10, 1, 8, 5]):
            res = 0
            for i, p in enumerate(A):
                self.add(p)
                res += i + 1 - self.sum(p)
            return res
    N, K = LI()
    A = [I()-K for _ in range(N)]
    S = [[0,i] for i in range(N+1)]
    for i in range(N):
        S[i+1][0] = S[i][0]+A[i]
    S.sort()
    prev = -inf
    cnt = -1
    for i in range(N+1):
        if S[i][0]==prev:
            S[i][0] = cnt
        else:
            prev = S[i][0]
            cnt += 1
            S[i][0] = cnt
    S.sort(key=lambda x:x[1])
    A = [0]*(1+N)
    for i in range(N+1):
        A[i] = S[i][0]
    bit = Bit(cnt+1)
    #print(A)
    ans = N*(N+1)//2 - bit.inversion(A)
    if ans<0:
        ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
"""
b := ruisekiwa
b[r]-b[l] >= (r-l)k
b[r]-rk >= b[l]-lk (1-indexed)
c := b[i]-ik
"""
b = [0 for _ in range(n)]
b[0] = a[0]
for i in range(1, n):
	b[i] = b[i-1]+a[i]

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

"""
cr >= cl なる ペア(l, r)の個数を求めたい.
for i in range(n), find (i,j)
"""


class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def search(self, a):
		tmpsum = 0
		i = 0
		k = (self.bitlen-1).bit_length()
		while k >= 0:
			tmpk = 2**k
			if i+tmpk <= self.bitlen-1:
				if tmpsum+self.bit[i+tmpk] < a:
					tmpsum += self.bit[i+tmpk]
					i += tmpk
			k = k-1
		return i+1
	
	def output(self, a):
		return self.query(a+1)-self.query(a)
	
	def listout(self):
		return self.bit
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)


def compress(arr):
	*XS, = set(arr)
	XS.sort()
	target = {e:i for i, e in enumerate(XS)}
	rtl = []
	for i in range(n):
		rtl.append(target[arr[i]])
	return rtl


d = compress(c)

bit = BIT([0 for _ in range(n)])
ans = 0
for i in range(n):
	bit.add(d[i], 1)
	ans += bit.query(d[i]+1)
	if c[i] < 0:
		ans -= 1
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+[int(input())-k for _ in range(n)]
sm=0
ac=[]
for ai in a:
    sm+=ai
    ac.append(sm)


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: Accepted

Solution code:
"""
方針
(1) 累積和s_i = a_0 + a_1 + ... + a_{i-1}をとる
(2) 部分和s_i_j = a_i + ... + a_{j-1} = s_j - s_iについて、平均がk以上であるとき、
        s_j - s_i >= k * (j-i) = k*j - k*i
    ->  s_j - k*j >= s_i - k*iとなる(i, j), i < jのペアを数えればよいので
    b_i = s_i - k*iを計算する
(3) b_iを座標圧縮して0~nの範囲に変換する (b_i -> c_iになるとする) (大小関係のみ重要なので)
(4) 0~nの変換においてBITを用いて、順次c_iの値をカウントしていく
"""

class BIT:
    def __init__(self, n):
        self.size = n + 1
        self.tree = [0] * (n + 2)
 
    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 submit():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]

    # 累積和を求める
    s = [0]
    for ai in a:
        s.append(s[-1] + ai)

    # biを求める
    b = [s[i] - k * i for i in range(n + 1)]

    # ciを求める
    b_dict = {}
    cnt = 0
    for be in sorted(b):
        if be not in b_dict:
            b_dict[be] = cnt
            cnt += 1
    c = [b_dict[be] for be in b]

    # BITでciの出現個数を逐次カウント
    bit = BIT(n)
    ans = 0
    for ce in c:
        ans += bit.sum(ce + 1)
        bit.add(ce + 1, 1)
    print(ans)

    
if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
from bisect import bisect_left
class SEGTree:
    def __init__(self,n):
        self.Unit=0
        i=1
        while(i<n):
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]+=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.SEG[i*2+1]+self.SEG[i*2+2]
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return c1+c2
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)
N,K=map(int,input().split())
a=[int(input()) for i in range(N)]
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=cum[i]+a[i]
B=[cum[i]-i*K for i in range(N+1)]

dic={}
li=sorted(B)
for i in range(N+1):
    dic[B[i]]=bisect_left(li,B[i])
seg=SEGTree(N+1)
ans=0
for i in range(N+1):
    ans+=seg.get(0,dic[B[i]]+1)
    seg.update(dic[B[i]],1)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

N,K=map(int,input().split())
a=[int(input()) for i in range(N)]
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=cum[i]+a[i]
B=[cum[i]-i*K for i in range(N+1)]

dic={}
li=sorted(B)
for i in range(N+1):
    dic[B[i]]=bisect_left(li,B[i])
bit=BIT(N+1)
ans=0
for i in range(N+1):
    ans+=bit.get(dic[B[i]]+1)
    bit.add(dic[B[i]],1)
print(ans)

Submission status: Accepted

Solution code:
class BIT():
    def __init__(self, N):
        self.N = N
        self.bit = [0 for i in range(N+1)]
    def add(self, a, w):
        x = a
        while 1:
            self.bit[x] += w
            x += x & -x
            if x > self.N:
                break
    def sum(self, a):
        ret = 0
        x = a
        while 1:
            ret += self.bit[x]
            x -= x & -x
            if x <= 0:
                break
        return ret
    
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}

N, K = map(int, input().split())
a = []
B = []
sum_a = 0
for i in range(N):
    a_ = int(input())
    a.append(a_)
    sum_a += a_
    B.append(sum_a - K*(i+1))

B_C = compress(B)
ans = sum([1 for i in B if i >= 0])
B = [B_C [i]+1for i in B] # 1-indexed

N = max(B)
f_tree = BIT(N)
for i in B:
    ret = f_tree.sum(i)
    f_tree.add(i, 1)
    ans += ret
print(ans)

Submission status: Accepted

Solution code:
# Meaningful mean
N, K = map(int, input().split())
d = []
for _ in range(N):
    a = int(input())
    d.append(a-K)
b = [0 for i in range(N)]
b[0] = [d[0], 0]
for i in range(1, N):
    d[i] += d[i-1]
    b[i] = [d[i], i]
rev = 0
for i in range(N):
    if d[i] < 0:
        rev += 1
para = 1

b.sort()

b[0][0] = para

for i in range(1, N):
    now = b[i-1][1]
    next_ = b[i][1]
    if d[now] == d[next_]:
        b[i][0] = para
    else:
        para += 1
        b[i][0] = para
b.sort(key=lambda x: x[1])
for i in range(N):
    d[i] = b[i][0]

# 0<=i<=j<=Nで a_i<=a_jを満たす物の個数をカウントする


ans = N*(N+1)//2
# 反転すうを求める


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

    def to_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)

    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)


ans = N*(N+1)//2

tree = BIT(N+1)

for index, p in enumerate(d):
    tree.add(p, 1)
    rev += index+1-tree.to_sum(p)
    
ans -= rev
print(ans)

Submission status: Accepted

Solution code:
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=list(map(int,input().split()))
a=[0]*(N+1)

for i in range(N):
    a[i+1]=int(input())

accum=[(x-K*i,i) for i,x in enumerate(accumulate(a))]
accum.sort(key=lambda x: 10**10*x[0]+x[1])
plst=[x+1 for _,x in accum]
bit=Bit(N+1)
ans=0

for i,p in enumerate(plst):
    bit.add(p,1)
    ans+=i+1-bit.sum(p)

print(N*(N+1)//2-ans)

Submission status: Accepted

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)
        self.n = n
    
    def add(self,val,idx):
        while idx < self.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: Accepted

Solution code:
from bisect import bisect_left


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

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

    def add(self, i, x):  # i > 0
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

d = [0] * (n+1)
d2 = {0}
for i in range(n):
    d[i+1] = d[i] + a[i] - k
    d2.add(d[i+1])

d2 = sorted(d2)

bit = Bit(len(d2))

ans = 0
for i in range(n+1):
    d2_i = bisect_left(d2, d[i])
    ans += bit.sum(d2_i+1)
    bit.add(d2_i+1, 1)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

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

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

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

    def search(self, value):
        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 //= 2
        return i + 1

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

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

sToI = {s: i for i, s in enumerate(sorted(list(set(accA))))}
tree = BIT(len(sToI))

ans = 0
for a in map(lambda a: sToI[a] + 1 ,accA):
    ans += tree.sum(a)
    tree.add(a)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

class BIT:
    def __init__(self, size, values):
        self.size = size
        self.tree = [0] * (size + 1)

        self.values = values
        self.values.sort()
        self.vToI = {v: i for i, v in enumerate(self.values, start=1)}

    def lowerValueIndex(self, v):
        return self.vToI[self.values[bisect_right(self.values, v) - 1]]

    def add(self, index):
        index = self.vToI[index]
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

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

    def search(self, value):
        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 //= 2
        return i + 1

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

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

values = accA + [10**18]
values += [-v for v in values]
values = list(set(values))
tree = BIT(len(values), values)

ans = 0
for i, a in enumerate(accA):
    ans += i - tree.sum(-a - 1)
    tree.add(-a)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())
jisho = defaultdict(int)
A = [int(input()) for _ in range(n)]
A = [0] + A
SA = list(accumulate(A))
T = [0] * (n + 1)
for i in range(n + 1):
    T[i] = (SA[i] - k * i, i)
T.sort()


class SegmentTree:
    ele = 0

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

    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    # def delay(self,):

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ST = SegmentTree(n + 1)
ans = 0
for val, i in T:
    ans += ST.query(0, i + 1)
    ST.update(i, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

# print (A)
for i in range(N):
    A[i + 1] += A[i]

B = sorted(A)
dic = dict()
for i, b in enumerate(B):
    dic[b] = i + 1

N += 1
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 a in A:
    b = dic[a]
    ans += total(b)
    # print ('tmp')
    add(b, 1)

print (ans)
# print (A)
# print (dic)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))

aa = []
for _ in range(N):
    a = int(input())
    aa.append(a - K)

raa = [0]
for a in aa:
    raa.append(raa[-1] + a)


class Searchable_BIT():
    def __init__(self, N):
        self.N = N
        self.node = [0] * (self.N + 1)
        self.cnt = 0

    def add(self, a):  # 要素 x を追加
        x = a
        self.cnt += 1
        while x <= self.N:
            self.node[x] += 1
            x += x & -x

    def delete(self, x):  # 要素 x を削除
        self.cnt -= 1
        while x <= self.N:
            self.node[x] -= 1
            x += x & -x

    def count(self, x):  # x以下の要素数
        tmp = 0
        while x > 0:
            tmp += self.node[x]
            x -= x & -x
        return tmp

    def get_maxval(self):
        return self.get_lower_i(self.cnt)

    def get_lower_i(self, i):  # i 番目に小さい要素を取得
        NG = -1
        OK = self.N
        while OK - NG > 1:
            mid = (OK + NG) // 2
            # print(OK,NG,self.count(mid))
            if self.count(mid) >= i:
                OK = mid
            else:
                NG = mid
        return OK


a2i = {a: i + 1 for i, a in enumerate(sorted(list(set(raa))))}
BIT = Searchable_BIT(len(a2i) + 5)

ans = 0
for i, a in enumerate(raa):
    ans += BIT.count(a2i[a])

    BIT.add(a2i[a])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect

def main():
	N,K = map(int,input().split())
	cum = [0]
	for _ in range(N):
		cum.append(cum[-1]+int(input())-K)

	s_cum = sorted(cum)

	def invNumCount(A):
		l = len(A)
		res = 0
		BIT = [0]*(l+1)

		def BIT_query(idx):
			res_sum = 0
			while idx > 0:
				res_sum += BIT[idx]
				idx -= idx&(-idx)
			return res_sum

		def BIT_update(idx,x):
			while idx <= l:
				BIT[idx] += x
				idx += idx&(-idx)
			return

		Ai = [None]*l
		for i,e in enumerate(A):
			Ai[e] = i
		for i,e in enumerate(Ai):
			res += i - BIT_query(e+1)
			BIT_update(e+1,1)
		return res

	d = {}
	pos = [None]*(N+1)
	for i,num in enumerate(cum):
		ind = bisect.bisect_left(s_cum,num)
		if num not in d:
			d[num] = 1
		else:
			ind += d[num]
			d[num] += 1
		pos[i] = N-ind

	print(invNumCount(pos))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

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

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

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

N, K = map(int, input().split())
a = [int(input()) for _ in range(N)]
cum = list(accumulate([0] + a))
v = [cum[i] - K*i for i in range(N+1)]
vs = list(set(v))
vs.sort()
compress = {vs[i]: i for i in range(len(vs))}
bit = BIT(len(vs))
ans = 0
for i in range(N+1):
    x = compress[v[i]]
    ans += bit.sum(x)
    bit.add(x, 1)
print(ans)

Submission status: Accepted

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

sm = 0
li = [[0, 0]]
for i, e in enumerate(a, 1):
    sm += e
    li.append([sm - k * i, i])

li.sort()
for i in range(n + 1):
    li[i][0] = i + 1

li.sort(key=lambda x: x[1])

bit = [0] * (n + 2)


def update(x):
    while x <= n + 1:
        bit[x] += 1
        x += x & (-x)


def sm(x):
    ret = 0
    while x:
        ret += bit[x]
        x -= x & (-x)

    return ret


ans = 0
for e, _ in li:
    ans += sm(e)
    update(e)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class BinaryIndexedTree:
    # 1-indexed
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    
    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def sum(self, i):
        res = 0
        while i:
            res += self.data[i]
            i -= i & -i
        return res
    
    def bisect_left(self, w):
        if w <= 0:
            return 0
        i = 0
        k = 1 << (self.n.bit_length() - 1)
        while 0 < k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k >>= 1
        return i + 1


def solve():
    N, K = map(int, rl().split())
    a = tuple(int(rl()) for _ in range(N))
    
    b = [0]
    acc = 0
    for i in range(N):
        acc += a[i]
        b.append(acc - (i + 1) * K)
    
    compress = {bi: idx for idx, bi in enumerate(sorted(b))}
    bit = BinaryIndexedTree(N + 1)
    
    ans = 0
    for bi in b:
        ans += bit.sum(compress[bi] + 1)
        bit.add(compress[bi], 1)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

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

def main():
    N, K = map(int, input().split())
    A_list = [int(input()) for i in range(N)]

    cumulative_sum = 0
    b_list = [(0, 0)]
    for i, i_A in enumerate(A_list, 1):
        cumulative_sum += i_A
        b_list.append((cumulative_sum - K*(i), i))

    b_list.sort()
    compression_number = 1
    c_list = [None]*(N+1)
    for _, i in b_list:
        c_list[i] = compression_number
        compression_number += 1

    bit = BIT(N+1)
    ans = 0
    for i_c in c_list:
        ans += bit.sum(i_c)
        bit.add(i_c, 1)

    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
import itertools
import bisect

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

cs = [0] + list(itertools.accumulate(a))

b = [v - k * i for i, v in enumerate(cs)]
# print(b)
#
# import numpy as np
# np.random.seed(1)
# b = list(np.random.randint(10, 20, size=10))

tmp = b.copy()
tmp.sort()
c = [bisect.bisect_left(tmp, v) for v in b]
n = len(c)

BIT = [0] * (n + 2)

up = lambda node: node + (node & (-node))
def add(x, p):
    p += 1
    while p <= n:
        BIT[p] += x
        p = up(p)

def find(p):
    p += 1
    s = 0
    while p:
        s += BIT[p]
        p -= p & (-p)
    return s


# print(c)
s = 0
for v in c:
    s += (find(v))
    add(1, v)
print(s)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())

alist=[]
slist=[0]
for i in range(N):
  a=int(input())
  alist.append(a)
  slist.append(slist[-1]+a)
#print(alist)
#print(slist)

splist=[]
for i in range(N+1):
  splist.append(slist[i]-i*K)
#print(splist)

#compress splist to spdic
sp_asc=sorted(list(set(splist)))
#print(sp_asc)
cnt=1
spdic={}
for sp in sp_asc:
  spdic[sp]=cnt
  cnt+=1
#print(spdic)
  
#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x,n):
  while idx <= n:
    BIT[idx] += x
    idx += idx&(-idx)
  return

answer=0
BIT=[0]*(len(spdic)+1)
for i in range(N+1):
  idx=spdic[splist[i]]
  answer+=BIT_query(idx)
  BIT_update(idx,1,len(spdic))
  #print(i,answer)
  
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


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

# 座標圧縮
zipped = {}
for i, xi in enumerate(sorted(set(t))):
    zipped[xi] = i + 1
m = len(zipped)
t2 = [0] * (n + 1)
for i in range(n + 1):
    t2[i] = zipped[t[i]]

ans = 0
bit = BIT1(m)
for i in range(n + 1):
    ans += bit.sum(t2[i])
    bit.add(t2[i], 1)
print(ans)

Submission status: Accepted

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

# 入力: 座標の配列
# 出力 MP[e] = i: 座標eはi番目に該当
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)

# Binary Indexed Tree (Fenwick Tree)
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):
        # assert i > 0
        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)