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:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i

N, K = map(int, input().split())
A = [int(input())-K for _ in range(N)]
from itertools import groupby, accumulate, product, permutations, combinations
cum = [0]+list(accumulate(A))
comp = lambda arr: {e: i+1 for i, e in enumerate(sorted(set(arr)))}
compcum = comp(cum)
for i in range(N+1):
  cum[i] = compcum[cum[i]]
bit = BIT(N+1)
ans = 0
for i in range(N+1):
  ans += bit.sum(cum[i])
  bit.add(cum[i],1)
print(ans)

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip



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

import sys
input = sys.stdin.readline
from itertools import accumulate
N, K = map(int, input().split())
A = []
for _ in range(N):
    A.append(int(input()))
S = [0] + list(accumulate(A))
T = []
for i, s in enumerate(S):
    T.append(s-K*i)
B = BitSet2(T,T)
print(N*(N+1)//2-B.flip_counter())

Submission status: Accepted

Solution code:
class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,k=map(int,input().split())
arr=[0]+[int(input()) for _ in range(n)]
for i in range(1,n+1):
  arr[i]+=arr[i-1]-k
s=set(arr)
key=sorted(list(s))
dic={}
for i in range(len(key)):
  dic[key[i]]=i+1
bit=BIT(len(key)+1)
ans=0
bit.add(dic[0],1)
for i in range(1,n+1):
  ans+=bit.sum(1,dic[arr[i]])
  bit.add(dic[arr[i]],1)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, k = map(int, input().split())

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

mp = defaultdict(int)
b = sorted(list(set(s)))
num = 1
for c in b:
	mp[c] = num
	num += 1
m = len(mp)
d = [0] * (m + 1)

def add(i):
	while i <= m:
		d[i] += 1
		i += i & -i
def qqq(i):
	res = 0
	while i > 0:
		res += d[i]
		i -= i & -i
	return res

ans = 0
for i in range(n + 1):
	ans += qqq(mp[s[i]])
	add(mp[s[i]])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
#BIT
BIT = [0] * (n + 10)
def add(i, x):
    while i <= (n + 10):
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = [0] + [int(input()) - k for i in range(n)]
a = list(accumulate(a))
b = sorted(a)
b.append(-float("inf"))
cnt = 0
dic = dict()
for i in range(n + 1):
    if b[i] != b[i - 1]:
        cnt += 1
        dic[b[i]] = cnt
answer = 0
for I in range(n + 1):
    answer += query(dic[a[I]])
    add(dic[a[I]], 1)
print(answer)

Submission status: Accepted

Solution code:
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(n,k,a):
  b=[x-k for x in a]
  tmp=0
  cb=[tmp]
  for x in b:
    tmp+=x
    cb.append(tmp)
  from bisect import bisect_right
  cbb=cb.copy()
  cbb.sort()
  cb=[bisect_right(cbb,x) for x in cb]
  bit=BIT(n+2)
  ans=0
  for x in cb:
    ans+=bit.sum(x)
    bit.add(x,1)
  return ans

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    # a - 1の場所にwを追加する
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    # a未満の数字が何個あるか
    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

N, K = getNM()
A = getArray(N)

# 連続部分列: imos, 尺取り法, セグ木, 数え上げdpなどが使えそう
# 算術平均がK以上であるものは何個あるでしょうか？ 尺取りっぽい
# → 平均なので尺取りではない　{100, 1 100...100}みたいな場合

# 平均なので各項をKで引いて見ようか
# N, K = 3, 6
# A = [7, 5, 7] の場合
# A = [1, -1, 1]になる 累計が0以上のもの → これだとO(n2)かかる
# 右端rを決めた時にペアになる左端lはいくつあるか

# N, K = 7, 26
# A = [10, 20, 30, 40, 30, 20, 10]の時
# imos = [0, -16, -22, -18, -4, 0, -6, -22]
# l ~ r区間の平均 = imos[r] - imos[l - 1] これが0以上なら
# = imos[r] >= imos[l - 1]なら
# imos[b] - imos[a] >= 0になるペアがいくつあるかをO(n)で

# つまり
# imos上のimos[i] = bについてより左側にb以下の数はいくつあるか

A = [i - K for i in A]
imos = [0]
for i in range(N):
    imos.append(imos[i] + A[i])
mi = min(imos)
imos = [i - mi for i in imos] # imosの全ての要素が0以上になるように調整
N += 1

# 座標圧縮BIT
# alter: A[i] → alt_A[i]
# rev: alt[i] → A[i]
def compress(array):
    s = set(array)
    s = sorted(list(s))
    alter = {}
    rev = {}
    for i in range(len(s)):
        alter[s[i]] = i
        rev[i] = s[i]
    return alter, rev

alter, rev = compress(imos)
limit = N + 1
bit = BIT(limit)
ans = 0
for i in range(N):
    # 自身以下の数字が左にいくつあるか
    ans += bit.get(alter[imos[i]] + 2) # 変換してから調べる
    bit.add(alter[imos[i]] + 1, 1) # 変換してからレコード

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    # a - 1の場所にwを追加する
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    # a未満の数字が何個あるか
    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

N, K = getNM()
A = getArray(N)

# 連続部分列: imos, 尺取り法, セグ木, 数え上げdpなどが使えそう
# 算術平均がK以上であるものは何個あるでしょうか？ 尺取りっぽい
# → 平均なので尺取りではない　{100, 1 100...100}みたいな場合

# 平均なので各項をKで引いて見ようか
# N, K = 3, 6
# A = [7, 5, 7] の場合
# A = [1, -1, 1]になる 累計が0以上のもの → これだとO(n2)かかる
# 右端rを決めた時にペアになる左端lはいくつあるか

# N, K = 7, 26
# A = [10, 20, 30, 40, 30, 20, 10]の時
# imos = [0, -16, -22, -18, -4, 0, -6, -22]
# l ~ r区間の平均 = imos[r] - imos[l - 1] これが0以上なら
# = imos[r] >= imos[l - 1]なら
# imos[b] - imos[a] >= 0になるペアがいくつあるかをO(n)で

# つまり
# bより左側にbより小さい数はいくつあるか

A = [i - K for i in A]
imos = [0]
for i in range(N):
    imos.append(imos[i] + A[i])
mi = min(imos)
imos = [i - mi for i in imos]
N += 1

# 座標圧縮BIT
# alter: A[i] → alt_A[i]
# rev: alt[i] → A[i]
def compress(array):
    s = set(array)
    s = sorted(list(s))
    alter = {}
    rev = {}
    for i in range(len(s)):
        alter[s[i]] = i
        rev[i] = s[i]
    return alter, rev

alter, rev = compress(imos)
limit = N + 1
bit = BIT(limit)
ans = 0
for i in range(N):
    # 自身以下の数字が左にいくつあるか
    ans += bit.get(alter[imos[i]] + 2)
    bit.add(alter[imos[i]] + 1, 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = [int(input()) for _ in range(n)]
for i in range(n):
    a[i] -= k
def cumsum(a):
    """※ aを破壊する
    l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    n = len(a)
    a.insert(0, 0)
    for i in range(1, n+1):
        a[i] = a[i-1]+a[i]
    return a
cumsum(a)
l = [a[0]]
ans = 0
### BIT binary
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

# a1,...,aiの和がv以上になる最小のindexを求める
def index(bit, v):
    i = 0
    k = 1
    n = len(bit)-1
    while 2*k<n:
        k *= 2
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    return i+1

from bisect import bisect_left
from bisect import bisect_left as bl, bisect_right as br

def press(l):
    # xs[inds[i]]==l[i]となる
    xs = sorted(set(l))
    inds = [None] * len(l)
    for i,item in enumerate(l):
        inds[i] = bisect_left(xs, item)
    return xs, inds
xs, inds = press(a)
bit = [0]*(len(inds)+1)
ans = 0
num = 0
for i in inds:
    ans += query(bit, i+1)
    add(bit, i+1, 1)
#     print(i, ii, xs[i])
    num += 1
print(ans)

Submission status: Accepted

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

from itertools import accumulate
C = [0]+A
C = list(accumulate(C))
#print(C)

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

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

    def sum(self, i, j):
        # return sum of [i, j)
        return self._sum(j) - self._sum(i)

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

B = list(set(C))
B.sort(reverse=True)
D = {}
for i, b in enumerate(B):
    D[b] = i

C = [D[c] for c in C]
bit = BIT(max(C)+1)
ans = 0
for c in C:
    ans += bit.sum(c, bit.n)
    bit.add(c, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
A = [0]  # 累積和
for i in range(N):
    A.append(A[-1]+I()-K)

# Ai<=Aj たる i<j の個数を数え上げる

B = sorted(list(set(A)))
d = {}
for i in range(len(B)):
    d[B[i]] = i+1

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

# Aを大小関係を保ち座標圧縮


class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return
    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


BIT = BIT([0]*(N+1))
ans = 0
for i in range(N+1):
    ans += BIT.query(A[i])
    BIT.update(A[i],1)
print(ans)

Submission status: Accepted

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

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

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

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

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

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

		return m

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

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

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

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

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

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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

    def get_sum(self, i=None):
        if i is None:
            i = self.size
        m = 0  # -INF
        while i > 0:
            m += self.tree[i]
            i -= i & -i
        return m

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

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

Y = sorted(set(X))
dic = {y:i+1 for i,y in enumerate(Y)}

BIT = Sum_Bit(N)
ans = 0
for i in range(N):
    ans += BIT.get_sum(dic[X[i]])
    if X[i] >= 0: ans += 1
    BIT.update(dic[X[i]], 1)
    
print(ans)

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())
b = [0]+[k-i for i in a]


from itertools import accumulate
sa = sorted(set(accumulate(b)))

zaatu = {ai:i for i,ai in enumerate(sa)}

v = 0
bit = BIT(n+1)

ans = 0
for i,ai in enumerate(a):
    ai -= k
    bit.add(zaatu[-v],1)    
    v += ai
    idx = zaatu[-v]
    
    res = i+1
    if idx: res -= bit.get_sum(idx-1)
    ans += res




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:
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:
import bisect

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i //= 2
    return

def find(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans += tree[s]
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans += tree[t]
            t = (t - 1) // 2
    return ans

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]
for i in range(n + 1):
    s[i] -= k * i
d = dict()
for i in s:
    if not i in d:
        d[i] = 1
    else:
        d[i] += 1
x = list(d.keys())
x.sort()
tree = make_tree(len(x))
for i in range(len(x)):
    update(i, d[x[i]])
cnt = 0
l = len(tree) // 2
for i in s:
    b = bisect.bisect_left(x, i)
    update(b, tree[l + b] - 1)
    cnt += find(b, l - 1)
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
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, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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 = 10 ** 9 + 7

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

    def add(self, i, w):
        x = i + 1
        self.total += w
        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 = [0] + list(accumulate([a - k for a in A]))
D  = {v:i for i,v in enumerate(sorted(A))}
bit = BIT(len(A))
c = 0
for a in A:
    c += bit.sum(D[a])
    bit.add(D[a], 1)

print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from itertools import permutations,product,combinations_with_replacement,groupby,accumulate,combinations
class BinaryIndexedTree():
    def __init__(self,N):
        self.N = N
        self.tree = [0] * (N + 1)
    
    def add(self,i,x):
        while i <= self.N:
            self.tree[i] += x
            i += (i & -i)
    
    def sum(self,i):
        ret = 0
        while i > 0:
            ret += self.tree[i]
            i -= (i & -i)
        return ret
    
    def lower_bound(self,x):#初めて和がx以上となるindex(0indexed)
        if x <= 0:
            return 0
        i = 0
        K = 1 << self.N.bit_length()
        while K > 0:
            if i + K <= self.N and self.tree[i + K] < x:
                x -= self.tree[i + K]
                i += K
            K >>= 1
        return i + 1
    
    def __str__(self):
        return ' '.join(map(str,self.tree))

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

    compress = list(sorted(set(A)))
    dic = {c:i for i,c in enumerate(compress,1)}
    bit = BinaryIndexedTree(len(compress))
    ans = N*(N + 1)//2
    for i,a in enumerate(A):
        j = dic[a]
        ans -= i - bit.sum(j)
        bit.add(j,1)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(input())for i in range(n)]
from itertools import accumulate
l=[0]+list(accumulate(a))
l=[j-k*i for i,j in enumerate(l)]

#座圧
a_to_i={a:i for i,a in enumerate(sorted(set(l)),1)}
b=[a_to_i[a]for a in l]

size=len(a_to_i)+2
bit=[0]*size

#x(index)の値にvを足す
#indexは1スタート
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x) #区間の長さ

#bit_1 + bit_2 + … + bit_nをO(log(n))で求める
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s

ans=0
for i in b:
    ans+=bit_sum(i)
    bit_update(i,1)
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:
import copy

class BinaryIndexedTree():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
 
    def initialize(self, seq):
        for i, x in enumerate(seq[1:], 1):
            self.tree[i] += x
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def __repr__(self):
        return self.tree.__repr__()
 
    def get_sum(self, i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i
 
    def find_kth_element(self, k):
        x, sx = 0, 0
        dx = (1 << self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= self.size:
                continue
            y = x + dx
            sy = sx + self.tree[y]
            if sy < k:
                x, sx = y, sy
        return x + 1

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

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

r2 = copy.copy(r)
r2.sort()

d = dict()
cnt = 1
d[r2[0]] = 1
for i in range(1,n+1):
    if r2[i] != r2[i-1]:
        cnt += 1
    d[r2[i]] = cnt
#print(d)

bit = BinaryIndexedTree(2*10**5+5)
ans = 0

for i in range(n,-1,-1):
    t = d[r[i]]
    ans += bit.get_sum(2*10**5+2)-bit.get_sum(t-1)
    bit.add(t, 1)

print(ans)