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:

#セグ木
from collections import deque
def f(L, R): return L + R #マージ
def g(old, new): return old+new #更新
zero = 0 #マージにおける零元

class segtree:
    def __init__(self, N, z): #要素数、零元
        self.M = 1
        while self.M<N: self.M *= 2
        self.dat = [z] * (self.M*2-1)
        self.ZERO = z

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

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

#Verify https://atcoder.jp/contests/abc157/submissions/11965304

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

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

Submission status: Accepted

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


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

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

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

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

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


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


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

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

Submission status: Accepted

Solution code:
# Treap
#平衡二分木　乱数を用いてできるだけ平衡を保つらしい　
#priorityには乱数を入れること
# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

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

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

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

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

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

def delete(val):
    global root
    x = root

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

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

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

import random

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

import random,sys

input=sys.stdin.readline

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

LEN=len(compression_dict)

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

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

print(ANS)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

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

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

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

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

    def get(self, k): #k個以下のときはINFを返す
        return self.value[self.bit.bisect_left(k) - 1]

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

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

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

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

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

import sys
input = sys.stdin.readline

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

cum = [0]

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

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

S = Set(V)

res = 0

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

print(res)

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

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

Submission status: Accepted

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

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

tmp = sorted(B)

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


N = len(B)
bit = [0] * (N + 1)
def total(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

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

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

print (ans)
# print (B)
# print (dic)
# print (bit)

Submission status: Accepted

Solution code:
#座標圧縮
#a=list
#flag=0...座圧済みa flag=1...座圧指標dict
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]

#-----BinaryIndexedTree-----(0-indexed)
#O(logN)で累積和取得と値の更新
#add(i,x)...i番目にxを加算
#sum(i,j)...[i,j]の累積和を取得
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

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

#################

# 全て-Kして，和が0以上かどうかを判定する
# 累積和の座圧→bitで出来る

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

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

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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
 
def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    #n:要素数
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    #i番目(0-indexed)の値にxを足す
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    #0からi番目までの値の和を求める
    def acc(self, i):
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

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

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

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

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

Submission status: Accepted

Solution code:
import bisect
#####segfunc######                                                              
def segfunc(x,y):
    return x+y

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

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

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

exit()

Submission status: Accepted

Solution code:
from itertools import accumulate as acc

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

sys.setrecursionlimit(10 ** 8)


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


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

    def __init__(self, x, init_val):  # 構築, init_valは配列の初期値(最小値のクエリならINF, 和なら0)
        self.init_val = init_val
        self.length = 2 ** ((len(x) - 1).bit_length())
        self.data = [init_val] * (2 + 1) * self.length
        for i in range(len(x)):
            self.data[i + self.length - 1] = x[i]
        for i in range(self.length - 2, -1, -1):
            self.data[i] = func(self.data[2 * i + 1], self.data[2 * i + 2])

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

    def replace(self, index, val):  # indexの値をvalに更新
        index += self.length - 1
        self.data[index] = val
        while index:
            index = (index - 1) // 2
            self.data[index] = func(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):  # 半開区間の最小値等を求める, 葉からさかのぼっていくイメージ。
        if right <= left:
            return self.init_val
        left += self.length - 1  # self.dataの位置に合わせる。
        right += self.length - 2  # self.dataの位置に合わせる。半開区間
        ans = self.init_val
        while right > left + 1:
            if left & 1 == 0:  # if left_index%2 == 0:
                ans = func(ans, self.data[left])
            if right & 1 == 1:  # if right_index%2 == 1:
                ans = func(ans, self.data[right])
                right -= 1
            left //= 2
            right = (right - 1) // 2
        if left == right:
            ans = func(ans, self.data[left])
        else:
            ans = func(func(ans, self.data[left]), self.data[right])
        return ans


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

Submission status: Accepted

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

def get(r):
    r += 1

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

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

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

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

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

v = [0]

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

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

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

ans = 0

for i in range(n + 1):
    ans += get(mp[v[i]])
    update(mp[v[i]], 1)

print(ans)

Submission status: Accepted

Solution code:
class BIT():
  def __init__(self,n):# 0-indexed
    self.n=n
    self.bit=[0]*(n+1)
  def add(self,i,x):
    i+=1
    while i<=self.n:
      self.bit[i]+=x
      i+=i&-i
  def _sum(self,i):
    s=0
    while i>0:
      s+=self.bit[i]
      i-=i&-i
    return s
  def get(self,i,j):# get sum between [i,j)
    return self._sum(j)-self._sum(i)
n,k=map(int,input().split())
a=[int(input()) for i in range(n)]
cumsum_a=[0]*(n+1)
for i in range(n):
  cumsum_a[i+1]=cumsum_a[i]+a[i]
for i in range(n+1):
  cumsum_a[i]-=k*i
  
def compress(list1):
  list2=sorted(set(list1))
  memo={value:index for index,value in enumerate(list2)}
  for i in range(len(list1)):
    list1[i]=memo[list1[i]]
  return list1
cumsum_a=compress(cumsum_a)
bit=BIT(n+1)
ans=0
for i in range(n+1):
  ans+=bit.get(0,cumsum_a[i]+1)
  bit.add(cumsum_a[i],1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = [0] * N
for i in range(N): a[i] = int(input())
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
#print(cs)
table = [0] * (N + 1)
for i in range(1, N + 1): table[i] = cs[i] - i * K
#print(table)
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

fwk = BIT(N + 1)

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

comtable = compress(table)

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

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

Submission status: Accepted

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


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


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

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

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


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

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

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


print(c)

Submission status: Accepted

Solution code:

def bitadd(a,w,bit): #aにwを加える(1-origin)

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

def bitsum(a,bit): #ind 0～aまでの和を求める

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


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

a = []

for i in range(N):

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


B = [0]

for i in range(N):

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

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

dic = {}

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

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

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

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

ans = 0

for i in range(N+1):

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

print (ans)

Submission status: Accepted

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

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

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

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

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

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

    # S[i] の転倒数を考えれば良く、そのために座圧する
    D={s:i for i,s in enumerate(sorted(set(S)))}
    for i in range(n+1):
        S[i]=D[S[i]]

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

    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

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

def main():
    n,k=MI()
    aa=np.zeros(n+1,dtype="i8")
    aa[0]=k
    for i in range(1,n+1):
        aa[i]=II()
    aa-=k
    cs=np.cumsum(aa)
    #print(aa)
    #print(cs)
    #座標圧縮
    ss=set()
    for s in cs:
        ss.add(s)
    enc={s:i for i,s in enumerate(sorted(ss))}
    #print(enc)
    #転倒数の要領で、自分より左にある自分以下の数の個数を数える
    bit=BitSum(len(ss))
    ans=0
    for s in cs:
        enc_s=enc[s]
        ans+=bit.sum(enc_s)
        bit.update(enc_s,1)
    print(ans)

main()

Submission status: Accepted

Solution code:
# 解説を見た

# https://tjkendev.github.io/procon-library/python/range_query/bit.html
# 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)


def main():
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

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

    acc = (0,) + tuple(accumulate(A))

    def compress(iter):
        convert = {x: i for i, x in enumerate(sorted(iter), start=1)}
        # BITで扱うので、1-indexedにする
        # 値kがa番目とa+1番目に含まれているとき、k:a->k:a+1で上書きされる
        return (convert[x] for x in iter)

    comacc = compress(acc)

    ret = 0

    b = BIT(N + 1)
    for x in comacc:
        ret += b.sum(x)
        b.add(x, 1)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 解説を見た

# https://tjkendev.github.io/procon-library/python/range_query/bit.html
# 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)


def main():
    from itertools import accumulate

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

    acc = (0,) + tuple(accumulate(A))

    def compress(iter):
        convert = {x: i for i, x in enumerate(sorted(iter), start=1)}
        # BITで扱うので、1-indexedにする
        # 値kがa番目とa+1番目に含まれているとき、k:a->k:a+1で上書きされる
        return (convert[x] for x in iter)

    comacc = tuple(compress(acc))

    ret = 0

    b = BIT(len(comacc))
    for x in comacc:
        ret += b.sum(x)
        b.add(x, 1)

    print(ret)


if __name__ == '__main__':
    main()