Problem p03275 (python)

Fixed submission:
from itertools import accumulate
from math import ceil
 
N = int(input())
A = list(map(int, input().split()))
 
if N == 1:
    print(A[0])
    exit()
 
 
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)  # Binaryの先頭の分
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2
 
    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]
 
    # 累積和をとる
    Binary = list(accumulate(Binary))
 
    # BITを初期化
    BIT.reset()
 
    # 転倒数っぽいものを数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)
 
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X
 
print(lo)

Buggy submission (verdict: Runtime Error):
import numpy as np

n = int(input())
lst = list(map(int, input().split()))

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 judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    lst_accum = []
    a = 0
    for i in lst_r:
        a += i
        lst_accum.append(a)
    min_a = min(lst_accum)
    lst_accum = [i - min_a + 1 for i in lst_accum]
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        if high == t:
            break
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[low])

Buggy submission (verdict: Runtime Error):
import numpy as np

n = int(input())
lst = list(map(int, input().split()))

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 judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    array = np.cumsum(np.array(lst_r))
    lst_accum = array - min(array) + 1
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        if high == t:
            break
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[t])

Buggy submission (verdict: Runtime Error):
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

            
def judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    array = np.cumsum(np.array(lst_r))
    lst_accum = array - min(array) + 1
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[t])