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: Time Limit Exceeded

Solution code:
from bisect import bisect_right,insort_right
import sys
def main():
    input=sys.stdin.readline
    n,k=map(int,input().split())
    a=[int(input()) for _ in range(n)]
    accum,idx=[],[]
    for i in range(n-1):
        a[i+1]+=a[i]
    for i in range(n):
        accum.append(a[i]-(i+1)*k)
    ans=0
    for i in range(n):
        if accum[i]>=0:
            ans+=1
        cnt=bisect_right(idx,accum[i])
        insort_right(idx,accum[i])
        ans+=cnt
    return print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,insort_left
import sys
def main():
    input=sys.stdin.readline
    n,k=map(int,input().split())
    a=[int(input()) for _ in range(n)]
    accum,idx=[],[]
    for i in range(n-1):
        a[i+1]+=a[i]
    for i in range(n):
        accum.append((a[i]-(i+1)*k,i))
    accum.sort()
    ans=0
    for i in range(n):
        if accum[i][0]>=0:
            ans+=1
        cnt=bisect_left(idx,accum[i][1])
        insort_left(idx,accum[i][1])
        ans+=cnt
    return print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,insort_left
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
accum,idx=[],[]
for i in range(n-1):
    a[i+1]+=a[i]
for i in range(n):
    accum.append((a[i]-(i+1)*k,i))
accum.sort()
ans=0
for i in range(n):
    if accum[i][0]>=0:
        ans+=1
    cnt=bisect_left(idx,accum[i][1])
    insort_left(idx,accum[i][1])
    ans+=cnt
print(ans)
#print(idx)
#print(accum)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
accum,idx=[],[]
for i in range(n-1):
    a[i+1]+=a[i]
for i in range(n):
    accum.append((a[i]-(i+1)*k,i))
accum.sort()
ans=0
for i in range(n):
    if accum[i][0]>=0:
        ans+=1
    cnt=bisect_left(idx,accum[i][1])
    idx.insert(cnt,accum[i][1])
    ans+=cnt
print(ans)
#print(idx)
#print(accum)

Submission status: Time Limit Exceeded

Solution code:
class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def query(self, l, r):
        res = self.element
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = self.func(res, self.seg[r-1])
            if l & 1:
                res = self.func(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

import sys
input = sys.stdin.readline
read = sys.stdin.read
from itertools import accumulate

def compress(arr):
    *XS, = set(arr)
    XS.sort()
    d = {e: i for i, e in enumerate(XS)}
    return [d[e] for e in arr]

n, k = map(int, input().split())
if n == 1:
  print(int(int(input()) >= k))
  exit()
A = list(map(lambda x:int(x)-k, read().split()))
L = [0] + list(accumulate(A))
L = compress(L)
seg = Segtree([0]*(max(L)+1), lambda x, y:x+y, 0)
ans = 0
for l in L:
  ans += seg.query(0, l+1)
  t = seg.get(l)
  seg.update(l, t+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
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])
d.reverse()
ans=0
b=[d[0]]
for i in range(n):
    bi=bisect.bisect_left(b,d[i+1])
    ans+=(i+1)-bi
    bisect.insort(b,d[i+1])
print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
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 = [int(input()) - K for _ in range(N)]
a = list(itertools.accumulate(a))
a = [0] + a
val = [-INF]
for i in sorted(a):
    if i > val[-1]:
        val.append(i)
seg = SegmentTree([0] * N, 0)
ans = 0
for i in val[1:]:
    for ind, l in enumerate(a):
        if l == i:
            ans += seg.query(0, ind)
            seg.replace(ind, 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = 1
seg = []

def get(a, b, k, l, r):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return seg[k]
    
    return get(a, b, k * 2 + 1, l, (l + r) // 2) + get(a, b, k * 2 + 2, (l + r) // 2, r)

def update(k, x):
    k += N - 1
    seg[k] += x

    while k > 0:
        k = (k - 1) // 2
        seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]
    
    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)}

while N < len(mp):
    N <<= 1

for i in range(N * 2 - 1):
    seg.append(0)

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

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

from itertools import accumulate
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = [int(input())-k for i in range(n)]
acc = [0]+list(accumulate(a))
acc_i = []
for i,x in enumerate(acc):
  acc_i.append((x,i+1))
acc_i.sort()
bit = Bit(n+2)
ans = 0
for i in range(n+1):
  x = acc_i[i][1]
  ans += n+1-x+bit.sum(x)
  bit.add(1,-1)
  bit.add(x+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
A=[0]
for i in range(N):
    a=int(input())
    A.append(a-K)
B=[A[0]]
for i in range(1,N+1):
    B.append(B[-1]+A[i])
#print(A)
#print(B)
ans=0
for i in range(1,N+1):
    for j in range(i,N+1):
        if B[j]-B[i-1]>=0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # 下からc番目(0-indexed)の数
    # O(log(N))
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()


import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
ans = 0
B = []
b = 0
for a in A:
    b += a-K
    B.append(b)
    if b >= 0:
        ans += 1

ind_to_co = [0] + sorted(B)
co_to_ind = {}
for i in range(N):
    co_to_ind[ind_to_co[i+1]] = i+1

bit = BITbisect(N)
for b in B:
    bit.insert(co_to_ind[b])

for b in B:
    ib = co_to_ind[b]
    bit.delete(ib)
    ans += bit.length() - bit.bisect_left(ib)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
n,k=map(int,input().split())
b=[0]*(n+1)
def f(x):
    c=0
    while x>0:
        c+=b[x]
        x-=x&-x
    return c
def g(x,a):
    while x<n+1:
        b[x]+=a
        x+=x&-x
for i in range(n):
    g(i+1,int(input())-k)
c=[0]
d=0
for i in range(1,n+1):
    t=f(i)
    k=br(c,t)
    c.insert(k,f(i))
    d+=i-k
print((n*(n+1))//2-d)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

class SegmentTree:
    def __init__(self, N):
        self.N = 2 * pow(2, N.bit_length()) - 1
        self.data = [0 for _ in range(2*self.N)]
    
    def update(self, k, x):
        k += self.N-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = sum([self.data[2*k+1], self.data[2*k+2]])
    
    # [l,r)
    def query(self, l, r):
        L = l + self.N
        R = r + self.N
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = sum([s, self.data[R-1]])
            if L & 1:
                s = sum([s, self. data[L-1]])
                L += 1
            L >>= 1; R >>= 1
        return s

    def node(self, k):
        return st.query(k, k+1)

def compress(arr):
    N = len(arr)
    narr = sorted(arr)
    pressed = [-1] * N
    for i in range(N):
        pressed[i] = bisect_left(narr, arr[i])
    return pressed
    

def accmulate(arr):
    N = len(arr)
    cs = [0]*(N+1)
    for i in range(N):
        cs[i+1] = cs[i] + arr[i]
    return cs

# [l,r)
def query(cs, l, r):
    return cs[r] - cs[l]

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

cs = accmulate(A)
cs = compress(cs)
st = SegmentTree(N)

ans = 0

for i in range(N+1):
    ans += st.query(0, cs[i] + 1)
    st.update(cs[i], st.node(cs[i]) + 1)

print(ans)

Submission status: Time Limit Exceeded

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)
    eps = 10 ** -6
    place = {0: 0}
    for i in range(N):
        a = int(input()) - K
        ac[i+1] = ac[i] + a + eps
        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: Time Limit Exceeded

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

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

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


N, K = map(int, input().split())
ac = [0] * (N + 1)
eps = 10 ** -6
place = {0: 0}
for i in range(N):
    a = int(input()) - K
    ac[i+1] = ac[i] + a + eps
    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)

Submission status: Time Limit Exceeded

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]]

import math
n_max=2*10**5
nn=int(math.log2(n_max))+1
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: Time Limit Exceeded

Solution code:
import bisect
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]
ans=0
BB.sort()
for i in reversed(range(1,n+1)):
  BB.remove(AA[i])
  ans+=i-bisect.bisect_left(BB,AA[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
A=[]
for i in range(n):
  A.append(int(input())-k)
AA=[0]*(n+1)
AA[-2]=A[-1]
for i in reversed(range(n-1)):
  AA[i]=AA[i+1]+A[i]
ans=0
B=[]
for i in range(n):
  B.append(AA[i])
  B.sort()
  ans+=(i+1)-bisect.bisect_left(B,AA[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

from scipy.stats import rankdata

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
A = np.array([K] + A)
# D[l-1] <= D[r] (l <= r) なら平均が K 以上。
D = (A - K).cumsum()


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


print(count(D))

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy

F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
A_order = {0}
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
    A_order |= {A[a+1]}
maxA = len(A_order)
A_order = list(A_order)
A_order.sort()

compressed_A = dict()
for i in range(maxA):
    compressed_A[A_order[i]] = i

bit = [0] * (maxA + 1)
total_inversion = 0
for a in A:
    b = compressed_A[a] + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    #total sum
    upper = maxA + 1
    upper_sum = 0
    while upper > 0:
        upper_sum += bit[upper - 1]
        upper -= upper & -upper

    #lower sum
    lower = compressed_A[a] + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += upper_sum - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
A_order = list(set(deepcopy(A)))
A_order.sort()

compressed_A = [None] * (N + 1)
for i in range(N + 1):
    compressed_A[i] = A_order.index(A[i])

maxA = len(A_order)
bit = [0] * (maxA + 1)
total_inversion = 0
for a in compressed_A:
    b = a + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    #total sum
    upper = maxA + 1
    upper_sum = 0
    while upper > 0:
        upper_sum += bit[upper - 1]
        upper -= upper & -upper

    #lower sum
    lower = a + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += upper_sum - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

class BinaryIndexedTree:
    def __init__(self, As):
        self.numPow2 = 2 ** (len(As)-1).bit_length()
        self.data = [0] * (self.numPow2+1)
        for iA, A in enumerate(As):
            self.addValue(iA, A)

    def addValue(self, iA, A):
        iA += 1
        while iA <= self.numPow2:
            self.data[iA] += A
            iA += iA & -iA

    def getSum(self, iA):
        iA += 1
        ans = 0
        while iA > 0:
            ans += self.data[iA]
            iA -= iA & -iA
        return ans


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

Bs = list(accumulate([0]+[A-K for A in As]))
iBs = list(range(N+1))
iBs.sort(key=lambda iB: Bs[iB])

BIT = BinaryIndexedTree([0]*(N+1))

ans = 0
for iB in iBs:
    BIT.addValue(iB, 1)
    ans += BIT.getSum(iB-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        if idx < self.size:
            self.bitree[idx] += val
            self.addval(idx + (idx&(-idx)), val)
            
    def getsum(self, idx:int):
        if idx <= 0:
            return 0
        else:
            return self.bitree[idx] + self.getsum(idx - (idx&(-idx)))
    
    def reset(self):
        self.bitree = [0]*self.size


def val2ord(a: list, rev=False):
    dic = {ai: i for i, ai in enumerate(sorted(a, reverse=rev))}
    return [dic[ai] for ai in a]


n,k = li()
a = [ni() for _ in range(n)]

acc = [0] + list(accumulate(a))

b = [acci - i*k for i,acci in enumerate(acc)]

c = val2ord(b)

bitree = BIT(n+1)

ans = 0

for ci in c:
    bitree.addval(ci+1, 1)
    ans += bitree.getsum(ci+1)-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect,insort
n,k = (int(i) for i in input().split())
a = [int(input())-k for i in range(n)]
b = [[0,0]]
for i in range(n): b.append([-(a[i]-b[-1][0]),-(i+1)])
b.sort()
q,ans,num = [-b[0][1]],0,1
for i,j in b[1:]:
	c = bisect(q,-j)
	ans+=num-c
	num+=1
	insort(q,-j,c,c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = map(int,input().split())
z = [0 for i in range(N+1)]
s = 0
for i in range(N):
	s += int(input())
	z[i+1] = s
cnt = 0
for (i,j) in itertools.combinations(range(N+1),2):
	if z[j]-z[i] >= K*(j-i):
		cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,K = map(int,input().split())
src = [int(input()) for i in range(N)]
if N == 1:
    print(int(src[0]>=K))
    exit()

cums = [0]
for a in src:
    cums.append(cums[-1] + a - K)

s_cums = sorted(cums)
cmp = []
for a in cums:
    i = bisect.bisect(s_cums, a)
    cmp.append(i-1)

bit = [0] * (N+1)
def bit_add(a,w):
    x = a
    while x <= N:
        bit[x] += w
        x += (x & -x)

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

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

Submission status: Time Limit Exceeded

Solution code:
tmp = list(map(int,input().split()))
n , k = tmp[0] , tmp[1]
lis = []
for i in range(n):
    lis.append(int(input()) - k)
anlis = [lis[0]]
ans = int(anlis[0] >= 0)
for i in range(1,n):
    m = lis[i]
    anlis = list(map(lambda x: x + m,anlis))
    anlis.append(m)
    ans += sum([j >= 0 for j in anlis])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


def main():
    N, K = map(int, input().split(" "))
    cnt = 0
    sum_arr = []
    s = 0
    for i in range(N):
        a = int(input()) - K
        s += a
        cnt += bisect.bisect(sum_arr, s)
        cnt += (s >= 0)
        bisect.insort(sum_arr, s)
    return cnt


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
#         print(a[i:j])
        if sum(a[i:j]) >= 0:
            ans += 1
            
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
#         print(a[i:j])
        if sum(a[i:j]) >= K*(j-i):
            ans += 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def meaningful_mean_2():
	n, k = map(int, raw_input().split(" "))
	a = []
	for i in range(n):
		a.append(int(raw_input()))
	ans = 0
	b = [0]*(n+1)
	current_sum = 0
	for i in range(n):
		current_sum = current_sum+a[i]
		b[i+1] = current_sum-(i+1)*k
	for i in range(0, n):
		for j in range(i+1, n+1):
			if b[j] >= b[i]:
				ans += 1
	print ans

if __name__ == "__main__":
	meaningful_mean_2()

Submission status: Time Limit Exceeded

Solution code:
def meanningful_mean():
	n, k = map(int, raw_input().split(" "))
	a = []
	for i in range(n):
		a.append(int(raw_input()))
	ans = 0
	for i in range(0, n):
		for j in range(i+1, n+1):
			if sum(a[i:j])/(j-i) >= k:
				ans += 1
	print ans

if __name__ == "__main__":
	meanningful_mean()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().rstrip("\n").split(" "))

from collections import defaultdict

h = []
total = 0
prev_counter = defaultdict(int)
for i in range(n):
  value = int(input()) 
  counter = defaultdict(int)
  diff = value - k
  if diff >= 0:
    total += 1
  counter[diff] = 1
  for key, count in prev_counter.items():
    if (key + diff) >= 0:
      total += count
    counter[key + diff] += count
  prev_counter = counter
print(total )

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n,k = LI()
    a = [I() - k for _ in range(n)]
    t = []
    ti = 0
    r = 0
    l = 0
    for c in a:
        if c >= 0:
            r += 1
        bi = bisect.bisect_left(t,-c - ti)
        ti += c
        r += l - bi
        bisect.insort_left(t,c-ti)
        l += 1

    return r



print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n,k = LI()
    a = [I() - k for _ in range(n)]
    t = []
    ti = 0
    r = 0
    for c in a:
        if c >= 0:
            r += 1
        bi = bisect.bisect_left(t,-c - ti)
        ti += c
        r += len(t) - bi
        bisect.insort_left(t,c-ti)

    return r



print(main())