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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

import numpy as np


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

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

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


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

Submission status: Runtime Error

Solution code:
import bisect
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_acc = [0]+list(accumulate(L))
    for i in range(N+1):
        L_acc[i] -= (i)*K

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

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

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

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


solve()


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


solve()

Submission status: Runtime Error

Solution code:
import bisect
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_acc = [0]+list(accumulate(L))
    for i in range(N+1):
        L_acc[i] -= (i)*K

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

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

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

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


solve()

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+1)

def sumation(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
    
def add(i, x):
    while i <= N:
        data[i] += x
        i += i & -i
ans = 0
for e, i in v:
    ans += sumation(i+1)
    add(i+1, 1)
    
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+2)

def sumation(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
    
def add(i, x):
    while i <= N+2:
        data[i] += x
        i += i & -i
ans = 0
for e, i in v:
    ans += sumation(i+1)
    add(i+1, 1)
    
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*(n+1)
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*n
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

buf=input().split(' ')
N=int(buf[0])
K=int(buf[1])
arr=np.zeros(N,dtype=np.int8)
for i in range(N):
    arr[i]=int(input())
arr=arr-K

mat=-np.ones((N,N))
for i in range(N):
    mat[i][i]=arr[i]
    
for j in range(1,N):
    mat[0][j]=mat[0][j-1]+mat[j][j]

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

    
tmp=np.sum(mat>=0)
one=np.sum(arr>=0)
print(int((tmp-one)/2+one))

Submission status: Runtime Error

Solution code:
import numpy as np

buf=input().split(' ')
N=int(buf[0])
K=int(buf[1])
arr=np.zeros(N,dtype=np.int8)
for i in range(N):
    arr[i]=int(input())
arr=arr-K

mat=-np.ones((N,N))
for i in range(N):
    mat[i][i]=arr[i]

for j in range(1,N):
    mat[0][j]=mat[0][j-1]+mat[j][j]
for i in range(1, N):
    for j in range(i+1,N):
        mat[i][j]=mat[i-1][j]-mat[i-1][i-1]

print(np.sum(mat>=0))

Submission status: Runtime Error

Solution code:
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

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

from itertools import accumulate,repeat

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

B = [0] + [sa-sk for sa,sk in zip(accumulate(int(input())), accumulate(repeat(K, N)))]

lookup = dict(((b,i+1) for i,b in enumerate(sorted(B))))

result = 0
bit = BinaryIndexedTree(N+1)

for b in B:
  c = lookup[b]
  result += bit.sum(c)
  bit.add(c,1)

print(result)

Submission status: Runtime Error

Solution code:
n, k = map(int, raw_input().split())
A = [int(raw_input())-k for i in xrange(n)]
su = 0
v = [(0, 0)]
for i in xrange(n):
    su += A[i]
    v.append((su, i+1))
v.sort()

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*n
        self.el = [0]*n
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i):
        return self.el[i]

ans = 0
bit = BIT(n+2)
for e, i in v:
    ans += bit.sum(i+1)
    bit.add(i+1, 1)
print ans

Submission status: Runtime Error

Solution code:
n, k = map(int, raw_input().split())
A = [int(raw_input())-k for i in xrange(n)]
su = 0
v = [(0, 0)]
for i in xrange(n):
    su += A[i]
    v.append((su, i+1))
v.sort()

data = [0]*(n+2)
def sum(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= n+2:
        data[i] += x
        i += i & -i
ans = 0
tmp = 0
for e, i in v:
    ans += sum(i+1)
    add(i+1, 1)
print ans