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 main():
    from sys import stdin
    input=stdin.readline
    from itertools import accumulate as ac

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

    # bit木を作る
    bit = [0]*(n+2)

    # aにwを足す
    def add(a, w):
        x = a
        while x < n+2:
            # print(x)
            bit[x] += w
            x += x & (-x)

    # aまでの和をとる
    def sum_(a):
        ret = 0
        x = a
        while x > 0:
            ret += bit[x]
            x -= x & (-x)
        return ret

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


main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

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

class BinaryIndexedTree() :
    def __init__(self, N) :
        self.size = N
        self.tree = [0] * (N + 1)
        
    def sum(self, i) :
        s = 0
        while i > 0 :
            s += self.tree[i]
            i -= i & -i
        return s
        
    def add(self, i, x) :
        while i <= self.size :
            self.tree[i] += x
            i += i & -i
            
ret = 0
BIT = BinaryIndexedTree(N + 5)
for i in range(N + 1) :
    ret += BIT.sum(s[i] + 1)
    BIT.add(s[i] + 1, 1)
    
print(ret)

Submission status: Accepted

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

acca = []

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


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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

# ざあつ
d = {j:i for i,j in enumerate(sorted(set(s)))}
bit = BIT_RSQ(len(d))
ans = 0
for i in range(n):
    # 一個前を足す
    bit.add(d[s[i]]+1, 1)
    ans += bit.sum(d[s[i+1]]+1)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

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

class BIT:

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

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

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

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

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

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

N, K = MAP()
# 予め-Kした状態で用意しておく
A = [a-K for a in LIST(N)]

# 累積和
acc = [0] + list(accumulate(A))
# 座標圧縮
zipped, _ = compress(acc)

bit = BIT(len(zipped))
cnt = 0
for a in acc:
    # 自分より左にある、自分の値以下の数(転倒数の数え上げ)
    cnt += bit.sum(zipped[a])
    bit.add(zipped[a], 1)
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

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

class BIT:

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

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

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

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

N, K = MAP()
# 予め-Kした状態で用意しておく
A = [a-K for a in LIST(N)]

# 累積和
acc = [0] + list(accumulate(A))
# 座標圧縮
zip_acc = {}
for i, a in enumerate(sorted(set(acc))):
    zip_acc[a] = i

bit = BIT(len(zip_acc))
cnt = 0
for a in acc:
    # 自分より左にある、自分の値以下の数(転倒数の数え上げ)
    cnt += bit.sum(zip_acc[a])
    bit.add(zip_acc[a], 1)
print(cnt)

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
#show_flg=True

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

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

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

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

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


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

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

# Sum a1 to ax 
def bit_sum(x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

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

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

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

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

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

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

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

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

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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


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

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

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


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

    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

import numpy as np


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

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

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


n, k = map(int, input().split())
aaa = [0] + list(map(int, sys.stdin))
acc = [a - i * k for i, a in enumerate(accumulate(aaa))]
values = sorted(set(acc))
dct = {v: i for i, v in enumerate(values, start=1)}
bit = Bit(len(values))
ans = 0
for d in acc:
    i = dct[d]
    ans += bit.sum(i)
    bit.add(i, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys

import numpy as np


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

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

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


n, k = map(int, input().split())
aaa = np.fromiter(sys.stdin, dtype=np.int64)
aaa = np.insert(aaa, 0, 0)
acc = np.add.accumulate(aaa) - np.arange(0, k * n + 1, k)
dct = {v: i for i, v in enumerate(np.unique(acc), start=1)}
bit = Bit(len(dct))
ans = 0
for d in acc:
    i = dct[d]
    ans += bit.sum(i)
    bit.add(i, 1)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    n = I()

    return

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

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

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

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_right

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

S = sorted(S)

#BIT
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


bit = Bit(N+1)

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

Submission status: Accepted

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

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

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

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

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

# 過去に自分以下の値が何回出てきているのか
def BIT_update(tree, x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

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

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

print(answer)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

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

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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

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

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

    def __len__(self):
        return self._size


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

# cumsum の最初を 0 にする
N += 1
# D[l-1] <= D[r] (l <= r) なら平均が K 以上。
D = list(itertools.accumulate([0] + [a - K for a in A]))


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


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


print(count(D))

Submission status: Accepted

Solution code:
import bisect
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

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

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

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

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

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


solve()

Submission status: Accepted

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

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

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


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


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

D = [0] * (N + 1)
d = defaultdict(list)
for i in range(len(B)):
    d[B[i]].append(i)

B = sorted(B)
k = 0
i = 0
while i < N + 1:
    m = len(d[B[i]])
    for l in d[B[i]]:
        D[l] = k
    k += 1
    i += m

bt = BIT(N + 1)
num = 0
for i in range(N + 1):
    num += bt.sum(D[i] + 1)
    bt.add(D[i], 1)
print(num)

Submission status: Accepted

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

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

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


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


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

D = [0] * (N + 1)
d = defaultdict(list)
for i in range(len(B)):
    d[B[i]].append(i)

B = sorted(B)
k = 0
i = 0
while i < N + 1:
    m = len(d[B[i]])
    for l in d[B[i]]:
        D[l] = k
    k += 1
    i += m

bt = BIT(N + 1)
num = 0
for i in range(N + 1):
    num += bt.sum(D[i] + 1)
    bt.add(D[i], 1)
print(num)

Submission status: Accepted

Solution code:
class BIT():

    def __init__(self, n):
        '''
        n = 要素数
        添字は i = 0 ~ n-1 となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        '''i番目の要素にxを加算する'''
        i = 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):
        '''[i, j)の和を求める'''
        return self._sum(j) - self._sum(i)


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

#いい感じに式変形した結果の配列をつくる
#cumsum_a[i] <= cumsum_a[j]を満たすi<jの組の個数が答えになる
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] = 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)

Submission status: Accepted

Solution code:
class BIT():

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

    def add(self, i, x):
        '''i番目の要素にxを加算する'''
        i = 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):
        '''[i, j)の和を求める'''
        return self._sum(j) - self._sum(i)


n, k = map(int, input().split())
a = [int(input()) for _ 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] = cumsum_a[i] - k*i

#座標圧縮したリストを返す
def compress(list1):
    len_list1 = len(list1)
    list11 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list11)}
    list2 = [0]*(len_list1)
    for i in range(len_list1):
        list2[i] = memo[list1[i]]
    return list2

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)

Submission status: Accepted

Solution code:
from itertools import accumulate
import bisect


class Bit():
    def __init__(self, N):
        self.size = N
        self.bit = [0] * (self.size+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 __str__(self):
        return str(self.bit)


N, K = map(int, input().split())
A = [-10**9] + [int(input()) for i in range(N)]

diff = [a - K for a in A]
diff = list(accumulate(diff))
graph = Bit(N+1)
temp = sorted(diff)
order = [bisect.bisect_right(temp, d) for d in diff]
ans = 0

for x in order:
    ans += graph.sum(x)
    graph.add(x, 1)

print(ans)