Problem: We will define the **median** of a sequence b of length M, as follows:    * Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.  For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.  Snuke comes up with the following problem.  You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new sequence m. Find the median of m.

Submission attempts (in order):

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

class BIT:
    def __init__(self, n):
        self.n = 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.n:
            self.bit[i] += x
            i += i&(-i)
            
a_sorted = sorted(list(set(a)))
left, right = 0, len(a_sorted) # number of unique elements of a
while right-left > 1: 
    mid = (left+right)//2 
    num = 0 # number of ranges with majority >= a_sorted[mid]
    bit = BIT(2*n+1) 
    sum_ = 0 # region sum
    bit.add(sum_+n, 1)
    for i in range(n): # O(n)
        sum_ += 1 if a[i] >= a_sorted[mid] else -1 # update region sum by comaprison
        num += bit.sum(sum_+n) # add #ranges by sum_+n: O(logn)
        bit.add(sum_+n, 1) # increment BIT element at sum_+n(=count of interested regions)
    

    # update search range
    if num > n*(n+1)//4:
        left = mid
    else:
        right = mid
print(a_sorted[left])


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

class BIT:
    def __init__(self, n):
        self.n = 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.n:
            self.bit[i] += x
            i += i&(-i)
            
left, right = 0, 10**9
geta = n+1
while right-left > 1:
    mid = (left+right)//2
    num = 0
    bit = BIT(2*n+1)
    sum_ = 0
    bit.add(sum_+geta, 1)
    for i in range(n):
        val = 1 if a[i] <= mid else -1
        sum_ += val
        num += bit.sum(sum_+geta-1) - bit.sum(0)
        bit.add(sum_+geta, 1)

    print(bit.bit)
    if num > n*(n+1)//4:
        right = mid
    else:
        left = mid
print(right)


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

a_sorted = sorted(set(a))+[10**18]
left, right = 0, len(a_sorted)-1

while right-left > 1:
    mid = (left+right)//2
    x = a_sorted[mid]

    count = [0]*(2*n+1)
    count[n+1] = 1
    i, accum, res = n+1, 1, 0

    for aa in a:
        if aa >= x:
            i += 1
            accum += count[i]
        else:
            accum -= count[i]
            i -= 1

        res += accum
        count[i] += 1
        accum += 1

    if res >= n*(n+1)//4:
        left = mid
    else:
        right = mid

print(a_sorted[left])


Verdicts: Wrong Answer

Wrong Answer

Accepted