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: Wrong Answer

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
#BIT
BIT = [0] * (n + 10)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = [int(input()) for i in range(n)]
a.insert(0, k)
a = list(map(lambda x:x - k, a))
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: Wrong Answer

Solution code:
from collections import Counter
from bisect import bisect_right

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

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

cum=[0]
for i in range(N):
  cum.append(cum[-1]+A[i])
  
c = Counter(cum[1:])
items = sorted(c.items(),reverse=True)

data=[(10**20,0)]
for k,num in items:
  data.append((k,data[-1][1]+num))

data = dict(data[::-1])
  
ans = 0
past=[]
for i in range(N):
  cu = cum[i+1]
  if data.get(cu):
    ans += data[cu]
    data[cu] -= 1
  if i == 0:
    past.append(cu)
    continue
  idx = bisect_right(past,cu)
  ans -= len(past)-idx
  past.insert(idx,cu)
  
print(ans)

Submission status: Wrong Answer

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

N, K = map(int, input().split())
a = []
B = []
same = 0
for i in range(N):
    a.append(int(input()))
    v = sum(a) - K*(i+1)
    if v in B:
        same += 1
    B.append(v)
B_ = compress(B)
ans = same
for i in range(N):
    if B[i] >= 0:
        ans += 1
    if i < B_[B[i]]:
        ans += i
    else:
        ans += B_[B[i]]
print(ans)

Submission status: Wrong Answer

Solution code:
def coordinate_compression(arr):
    return {v: k for k, v in enumerate(sorted(set(arr)))}


n, k = map(int, input().split())
bit = [0] * (n * 2 + 4)


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


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


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

d = coordinate_compression(a)
ans = 0
for x in a:
    ans += query(d[x] + 1)
    add(1, d[x] + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
def coordinate_compression(arr):
    return {v: k for k, v in enumerate(sorted(set(arr)))}


n, k = map(int, input().split())
bit = [0] * (n + 4)


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


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


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

d = coordinate_compression(a)
ans = 0
for x in a:
    ans += query(d[x] + 1)
    add(1, d[x] + 1)
print(ans)

Submission status: Wrong Answer

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

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

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

hq=[]
heapq.heappush(hq,0)
answer=0
for i in range(1,N+1):
  x=bisect.bisect(hq,splist[i])
  answer+=x
  heapq.heappush(hq,splist[i])
  
print(answer)

Submission status: Wrong Answer

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],n)
    update(a[i+1],query(a[i+1],a[i+1]+1)+1)
print(ans)
#query(0,i)

exit()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
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],n)
    update(a[i],query(a[i],a[i]+1)+1)
print(ans)
#query(0,i)

Submission status: Wrong Answer

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 = list(dict.fromkeys(sorted(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, 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: Wrong Answer

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 * (i+1)
    place[ac[i+1]] = i+1
ac.sort()
ac_cmpr = [0] * (N+1)
for i in range(N+1):
    ac_cmpr[place[ac[i]]] = i + 1
bit = Bit(N*2)
bit.add(ac_cmpr[0], 1)
ans = 0
for i in range(1, N+1):
    ans += bit.sum(ac_cmpr[i])
    bit.add(ac_cmpr[i], 1)

print(ans)

Submission status: Wrong Answer

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 * (i+1)
    place[ac[i+1]] = i+1
ac.sort()
ac_cmpr = [0] * (N+1)
for i in range(N+1):
    ac_cmpr[place[ac[i]]] = i + 1
bit = Bit(N+2)
bit.add(ac_cmpr[0], 1)
ans = 0
for i in range(1, N+1):
    ans += bit.sum(ac_cmpr[i])
    bit.add(ac_cmpr[i], 1)

print(ans)

Submission status: Wrong Answer

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 * (i+1)
    place[ac[i+1]] = i+1
ac.sort()
ac_cmpr = [0] * (N+1)
for i in range(N+1):
    ac_cmpr[place[ac[i]]] = i + 1
bit = Bit(N+1)
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: Wrong Answer

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 * i
    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+1)
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: Wrong Answer

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


def brute():
    N, K = map(int, input().split())
    L = [int(input()) for _ in range(N)]
    ans = 0
    for i in range(N):
        for j in range(i, N):
            if sum(L[i:j+1])/(j+1-i) >= K:
                ans += 1

    print(ans)


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

    L_acc = [0]+list(accumulate(L))
    ans = 0
    for i in range(N):
        for j in range(i, N):
            if L_acc[j+1]-L_acc[i] >= 0:
                ans += 1
    print(L_acc)


solve()

Submission status: Wrong Answer

Solution code:
import sys,bisect,math
input = sys.stdin.readline

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
# i と x が与えられたとき ai += x とする ( O(log n) )
def bitadd(bit,i,x):
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit

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

#b[j+1]-b[i]:a[i]~a[j]
b = [0]
for i in range(n):
    b.append(b[-1]+a[i])

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

d = sorted(c)
for i in range(n+1):
    k = bisect.bisect_left(d,c[i])
    d[k] = d[k]
    c[i] = k+1
#print(c)
n_ = int(math.log2(n+1)) + 1
bit = [0] * (2**n_+1)
ass = 0
for j in range(n+1):
    ass += j-bitsum(bit,c[j])
    #bitsum(bit,a[j]): j-1番目までの中でa[j]以下のもの
    bit = bitadd(bit,c[j],1)
print(n*(n+1)//2-ass)

Submission status: Wrong Answer

Solution code:
import sys,bisect,math
input = sys.stdin.readline

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
# i と x が与えられたとき ai += x とする ( O(log n) )
def bitadd(bit,i,x):
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit

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

#b[j+1]-b[i]:a[i]~a[j]
b = [0]
for i in range(n):
    b.append(b[-1]+a[i])

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

d = sorted(c)
for i in range(n+1):
    k = bisect.bisect_left(d,c[i])
    d[k] = d[k]
    c[i] = k+1
print(c)
n_ = int(math.log2(n+1)) + 1
bit = [0] * (2**n_+1)
ass = 0
for j in range(n+1):
    ass += j-bitsum(bit,c[j])
    #bitsum(bit,a[j]): j-1番目までの中でa[j]以下のもの
    bit = bitadd(bit,c[j],1)
print(n*(n+1)//2-ass)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
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([b[-1][0]+a[i],i+1])
b.sort()
num,c = 1,[[b[0][1],1]]
for i in range(1,n+1):
	if b[i][0]!=b[i-1][0]: num+=1
	c.append([b[i][1],num])
c,d,ans = sorted(c),[0]*(n+2),0
def add(i):
	while i<=n:
		d[i] += 1
		i += i & -i
def get(i):
	s = 0
	while i:
		s += d[i]
		i -= i & -i
	return s
for i,j in c:
	ans+=get(j)
	add(j)
print(ans)

Submission status: Wrong Answer

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

diff = [a - K for a in A]
diff = list(accumulate(diff))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [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):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(len(set(A)))

diff_sorted = {a: i for i, a in enumerate(sorted(list(set(A))), start=1)}
ans = 0

for j, a in enumerate(A):
    ans += BIT.sum(diff_sorted[a]) + (diff[j] >= 0)
    BIT.add(diff_sorted[a], 1)

print(ans)

Submission status: Wrong Answer

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

diff = [a - K for a in A]
diff = list(accumulate(diff))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [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):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)

diff_sorted = {a: i for i, a in enumerate(sorted(A), start=1)}
ans = 0
for j, a in enumerate(A):
    ans += BIT.sum(diff_sorted[a]) + (diff[j] >= 0)
    BIT.add(diff_sorted[a], 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N, K = map(int, input().split())
A = []
sumA = 0
heapq.heappush(A, [0, 0])
for i in range(N):
  sumA += int(input()) - K
  heapq.heappush(A, [sumA, i + 1])
cnt = 0
BIT = [0] * (N + 1)
while A:
  a = heapq.heappop(A)[1]
  i = 1
  for bit in bin(a)[2:][::-1]:
    cnt += BIT[i - 1] * int(bit)
    i *= 2
  a += 1
  while a <= N + 1:
    BIT[a - 1] += 1
    a += a & (-a)
print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [[0, 0]] * (N + 1)
sumA = 0
for i in range(N):
  sumA += int(input()) - K
  A[i + 1] = [sumA, i + 1]
A.sort()
B = [0] * (N + 1)
for i in range(N + 1):
  B[i] = A[i][1]
cnt = 0
BIT = [0] * (N + 1)
for b in B:
  i = 1
  for bit in bin(b)[2:][::-1]:
    cnt += BIT[i - 1] * int(bit)
    i *= 2
  b += 1
  while b <= N + 1:
    BIT[b - 1] += 1
    b += b & (-b)
print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [[0, 0]] * (N + 1)
sumA = 0
for i in range(N):
  sumA += int(input()) - K
  A[i + 1] = [sumA, i + 1]
A.sort()
B = [0] * (N + 1)
for i in range(N + 1):
  B[i] = A[i][1]
cnt = 0
BIT = [0] * (N + 1)
for b in B:
  for i, bit in enumerate(bin(b)[2:][::-1]):
    cnt += BIT[2 ** i - 1] * int(bit)
  b += 1
  while b <= N + 1:
    BIT[b - 1] += 1
    b += b & (-b)
print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [0] * (N + 1)
sumA = 0
for i in range(N):
  sumA += int(input()) - K
  A[i + 1] = sumA
B = [0] * (N + 1)
SA = sorted([[a, i] for i, a in enumerate(A)])
for i in range(N + 1):
  B[i] = SA[i][1]
cnt = 0
BIT = [0] * (N + 1)
for b in B:
  for i, bit in enumerate(bin(b)[2:][::-1]):
    cnt += BIT[2 ** i - 1] * int(bit)
  b += 1
  while b <= N + 1:
    BIT[b - 1] += 1
    b += b & (-b)
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate

inf = 1<<60
ans = 0

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = [int(sys.stdin.readline().rstrip()) - k for i in range(n)]
    s = [0] + list(accumulate(a))

    print(ans)

def MergeSort(a):
    if len(a) == 1:
        return a

    apre = MergeSort(a[:len(a)//2])
    asuf = MergeSort(a[len(a)//2:])

    res = merge(apre, asuf)

    return res

def merge(a, b):
    global ans
    na = len(a)
    nb = len(b)

    a.append(-inf)
    b.append(-inf)

    la = 0
    lb = 0

    res = []

    for i in range(na + nb):
        if a[la] <= b[lb]:
            ans += na - la
            res.append(b[lb])
            lb += 1
        else:
            res.append(a[la])
            la += 1

    return res

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

def upper_bound(x):
    i = rank = 0
    n = len(S)
    while True:
        if 2*i + 2 < n and S[2*i + 2] <= x:
            i = 2*i + 2
        elif 2*i + 1 < n and S[2*i + 1] <= x:
            i = 2*i + 1
        elif i < n and S[i] >= x:
            return i + 1
        else:
            return i
    
N, K = map(int, raw_input().split())
a = [int(raw_input()) - K for i in xrange(N)]

S = []
s = ans = 0
for i in xrange(N):
    s += a[i]
    if s >= 0: ans += 1
    ans += upper_bound(-s)
    heapq.heappush(S, s)

print ans

Submission status: Time Limit Exceeded

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(X)
dic, i = {}, 1
while len(Y):
    y = Y.pop(0)
    dic[y] = i
    if len(Y) >= 1 and Y[0] > y:
        i += 1
Z = list(map(lambda x: dic[x], X))

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n, k = map(int, input().split())
total = 0
s_k = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    a = int(input())
    total += a
    s_k[i] = total - k * i

lst = []
ans = 0
for i, num in enumerate(s_k[::-1]):
    pos = bisect_left(lst, num)
    ans += i - pos
    lst = lst[:pos] + [num] + lst[pos:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from itertools import accumulate
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = [int(input()) - k for _ in range(n)]
    summary = list(accumulate(a))
    ans = n - bisect_left(sorted(summary), 0)
    for i in range(n - 1):
        tmp = summary[i:]
        tmp.sort()
        ans += n - i - 1 - bisect_left(tmp, summary[i])

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from itertools import accumulate
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = [int(input()) - k for _ in range(n)]
    ans = 0
    for i in range(n):
        ans += n - i - bisect_left(sorted(list(accumulate(a[i:]))), 0)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = [int(input()) - k for _ in range(n)]
    ans = 0
    for i in range(n):
        tmp = a[i]
        if tmp >= 0:
            ans += 1
        for j in range(i + 1, n):
            tmp += a[j]
            if tmp >= 0:
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

class SegTree():
    def segfunc(self, x, y):
        return x + y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, k = map(int, input().split())
    cum = [None]*(n+1)
    cum[0] = 0
    for i in range(1, n+1):
        cum[i] = int(input())
        cum[i] += cum[i-1]
    for i in range(n+1):
        cum[i] -= k*i
    srt = deepcopy(cum)
    srt.sort()
    dic = {}
    cnt = 0
    for i in range(n+1):
        if not srt[i] in dic:
            dic[srt[i]] = cnt
            cnt += 1
    tmp = [0]*cnt
    tmp[dic[cum[0]]] += 1
    seg = SegTree(0, cnt, tmp)
    ans = 0
    for i in range(1, n+1):
        p = dic[cum[i]]
        ans += seg.query(0, p+1)
        tmp[p] += 1
        seg.update(p, tmp[p])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)

	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def search(self, a):
		tmpsum = 0
		i = 0
		k = (self.bitlen-1).bit_length()
		while k >= 0:
			tmpk = 2**k
			if i+tmpk <= self.bitlen-1:
				if tmpsum + self.bit[i+tmpk] < a:
					tmpsum += self.bit[i+tmpk]
					i += tmpk
			k = k - 1
		return i+1
	
	def output(self, a):
		return self.query(a+1)-self.query(a)
	
	def listout(self):
		return self.bit
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

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

d = compress(c)

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

Submission status: Time Limit Exceeded

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

def rec(l):
    ll=len(l)
    if ll<=1:
        return 0
    l1=l[:ll//2]
    l2=l[ll//2:]
    res=rec(l1)+rec(l2)
    l1.sort()
    l2.sort()
    i2=0
    for i in range(len(l1)):
        while i2<len(l2) and l2[i2]<l1[i]:
            res+=len(l1)-i
            i2+=1
    return res
print(n*(n+1)//2-rec(ac))

Submission status: Time Limit Exceeded

Solution code:

#セグ木
import queue
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 = queue.Queue()
        q.put([l, r, 0])
        ret = self.ZERO
        while not q.empty():
            tmp = q.get()
            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.put([L, (L+R)//2, tmp[2]*2+1])
                q.put([(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

#verify https://atcoder.jp/contests/arc075/submissions/12296796

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)