Problem:


Score : 700 points

Problem Statement

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.

Constraints

1 \leq N \leq 10^5

a_i is an integer.

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the median of m.

Sample Input 1

3
10 30 20

Sample Output 1

30

The median of each contiguous subsequence of a is as follows:

The median of (10) is 10.

The median of (30) is 30.

The median of (20) is 20.

The median of (10, 30) is 30.

The median of (30, 20) is 30.

The median of (10, 30, 20) is 20.

Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.

Sample Input 2

1
10

Sample Output 2

10

Sample Input 3

10
5 9 5 9 8 9 3 5 4 3

Sample Output 3

8



Sample input:
3
10 30 20


Sample output:
30

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, range(n)))
    else:
        xx.sort()
        yy = xx[n/2 - 1: n/2 + 2]
        print(random.choice(yy))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    if n == 1: return a[0]

    d = dict(zip(sorted(set(a)), range(len(a))))

    def check(num):
        a1 = [0]*(n+1)
        a2 = [0]*(n+1)
        for i, ai in enumerate(a):
            if ai < num:
                a1[i+1] = a1[i]+1
                a2[i+1] = a2[i]
            else:
                a1[i+1] = a1[i]
                a2[i+1] = a2[i]+1
        ad = [a2[i]-a1[i]+10**5+1 for i in xrange(n+1)]

        bit = BinaryIndexedTree(2*10**5+1)
        cnt = 0
        for i in xrange(n+1):
            cnt += bit.sum(ad[i])
            bit.add(ad[i], 1)
        # print num, cnt

        return n*(n-1)/2 - cnt <= cnt

    mi = 0
    ma = 10**9+1

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(mid):
            mi = mid
        else:
            ma = mid

    return mi


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in range(size + 1)]
        self.size = size

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

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
N= int(input())
a=[int(i) for i in input().split()]
b=sorted(a)
if N==3:
    print(b[2])
elif N%2==0 and N<9:
    print(b[N//2])
elif N%2==0 and N>9:
    print(b[N//2 + 1])
elif N>6:
    print(b[N//2]+1)
else:
    print(b[N//2])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
l = 1
r = 2
c = [0] * n
ll = 0
lr = n - 1
while ll <= lr:
    c[lr] = r
    c[ll] = l
    lr -= 1
    ll += 1
    r += 2
    l += 2
t = sum(c) / 2
i = 0
while True:
    t -= c[i]
    if t <= 0:
        if len(a) > 1:
            print(a[i + 1])
        else:
            print(a[i])
        break
    i += 1

Submission status: Wrong Answer

Solution code:
i=int(input())*2//3
s=input().split()
l=[]
for c in s:
    l.append(int(c))
l.sort()
print(l[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
if n == 1:
    print(a[0])
else:
    print(a[n // 2 + 1])

Submission status: Wrong Answer

Solution code:
import statistics
# S = input()
N = int(input())
A = list(map(int, input().split()))
# LR = [list(map(int, input().split())) for _ in range(M)]

ans = 0

if N == 1:
    ans = A[0]
else:

    ar = []
    ar.append(statistics.median_high(A))
    for i in range(len(A)-1):
        ar.append(A[i])
        if A[i] >= A[i+1]:
            ar.append(A[i])
        else:
            ar.append(A[i+1])
    ar.append(A[N-1])
    ans = statistics.median_high(ar)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A=list(map(int,input().split()))

def get_middle(_list):
    return list(sorted(_list))[len(_list)//2]

def dict_middle(d):
    items = sorted(d.items())
    length = sum(map(lambda x:x[1],items))
    tmp =0
    for key,val in items:
        tmp+=val
        if tmp>=length//2+1:
            return key

def guchoku():
    M = []
    for i in range(N):
        for j in range(i+1,N+1):
            M.append(get_middle(A[i:j]))
    return get_middle(M)

INF = float('inf')
d = defaultdict(int)

for i in range(1,N+1):
    if i%2==0:
        d[INF] +=  N-i+1
for i in range(N):
    val = A[i]
    count = N+ min(i,N-i-1)
    d[val] +=count


print(dict_middle(d))

Submission status: Time Limit Exceeded

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

def med(x):   
    return sorted(x)[len(x)//2]

m = []
for l in range(n):
    for r in range(l,n):
        m += [med(a[l:r+1])]

print(med(m))

Submission status: Time Limit Exceeded

Solution code:
def cordineatecompression(list):
    n=len(list)
    test=[(list[i],i) for i in range(0,n)]
    ans=[-1 for i in range(0,n)]
    test.sort()
    co=1
    val=test[0][0]
    ans[test[0][1]]=co
    for i in range(1,n):
        if val==test[i][0]:
            ans[test[i][1]]=co
        else:
            val=test[i][0]
            co+=1
            ans[test[i][1]]=co
    return ans

N=int(input())
A=list(map(int,input().split()))

def median(num):
    data=[0]*N
    for i in range(N):
        if A[i]>num:
            data[i]=1
        else:
            data[i]=-1
    for i in range(1,N):
        data[i]+=data[i-1]
    data=[0]+data
    data=cordineatecompression(data)

    ans=0

    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**9
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)

Submission status: Time Limit Exceeded

Solution code:
def cordineatecompression(list):
    n=len(list)
    test=[(list[i],i) for i in range(0,n)]
    ans=[-1 for i in range(0,n)]
    test.sort()
    co=1
    val=test[0][0]
    ans[test[0][1]]=co
    for i in range(1,n):
        if val==test[i][0]:
            ans[test[i][1]]=co
        else:
            val=test[i][0]
            co+=1
            ans[test[i][1]]=co
    return ans

N=int(input())
A=list(map(int,input().split()))

def median(num):
    data=[0]*N
    for i in range(N):
        if A[i]>num:
            data[i]=1
        else:
            data[i]=-1
    for i in range(1,N):
        data[i]+=data[i-1]
    data=[0]+data
    data=cordineatecompression(data)


    ans=0

    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**12
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    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, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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

def solve(val):
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = 10**9 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    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, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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

def solve(val):
    ruiseki = [0] * (n + 1)
    for i in range(n):
        if a[i] >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    bit = BIT(n + 1)
    res = 0
    for i, num in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= (cnt + 1) // 2:
            return True
    return False

ok = 0
ng = 10**9 + 1
cnt = 0
for i in range(n):
    cnt += n - i
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    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, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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

def solve(val):
    ruiseki = [0] * (n + 1)
    for i in range(n):
        if a[i] >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    bit = BIT(n + 1)
    res = 0
    for i, num in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
    if res >= (cnt + 1) // 2:
        return True
    else:
        return False

ok = 0
ng = 10**9 + 1
cnt = 0
for i in range(n):
    cnt += n - i
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

N = int(input())
As = list(map(int, input().split()))

Bs = sorted(As)
M = N*(N+1)//2

def isOK(mid):
    Am = Bs[mid]
    Ss = [1 if A >= Am else -1 for A in As]
    Ss = list(accumulate([0]+Ss))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    iSs = list(range(N+1))
    iSs.sort(key=lambda iS: Ss[iS])
    odrSs = [0]*(N+1)
    for odrS, iS in enumerate(iSs):
        odrSs[iS] = odrS

    num = 0
    for odrS in odrSs:
        num += getSum(odrS)
        addValue(odrS, 1)
    return num >= (M+1)//2


ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(Bs[ok])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

N = int(input())
As = list(map(int, input().split()))

M = N*(N+1)//2

def isOK(mid):
    Ss = [1 if A >= mid else -1 for A in As]
    Ss = list(accumulate([0]+Ss))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    iSs = list(range(N+1))
    iSs.sort(key=lambda iS: Ss[iS])
    odrSs = [0]*(N+1)
    for odrS, iS in enumerate(iSs):
        odrSs[iS] = odrS

    num = 0
    for odrS in odrSs:
        num += getSum(odrS)
        addValue(odrS, 1)
    return num >= (M+1)//2


ng, ok = 10**9+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input() )
M = input().split() 

M=[int(a) for a in M]
M=np.array(M)
medians=[]
for i in range(len(M)):
    for j in range(i,len(M),1):
        m=M[i:j+1]
        m=np.sort(m)
        mid=int(len(m)/2)
        medians.append(m[mid])
medians=np.sort(np.array(medians))
mid2=int(len(medians)/2)
print(medians[mid2])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = max(a)+1
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in a]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+2 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
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

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))

Submission status: Time Limit Exceeded

Solution code:
# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
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

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

N, = map(int, input().split())
As = list(map(int, input().split()))

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = list(map(lambda a: 1 if a>=x else -1, As))
    xs = Bs[:]
    Bs = [0] + list(accumulate(Bs))
    mn = min(Bs)
    Bs = list(map(lambda x : x + max(0, -mn) + 1, Bs))
    #print(x, As, xs, Bs)
    return -tento(list(Bs))

M = (N*(N+1))//2
print(bsearch((-M//2) , min(As), max(As), f))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = n*(n+1)//2
k = m//2 +1
ok = max(a)
no = 0
a.sort()

m = []
for i in range(n):
    for j in range(i+1,n):
        s = (i+j)//2+1
        m.append(a[s])
m.sort()
while ok - no > 1:
    count = 0
    mid = (ok+no)//2
    for i in range(len(m)):
        if m[i] <= mid:
            count += 1
        else:
            break
    if count >= k:
        ok = mid
    else:
        no = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = n*(n+1)//2
k = m//2 +1
ok = max(a)
no = 0
a.sort()

m = []
for i in range(n):
    for j in range(i+1,n):
        s = (i+j)//2+1
        m.append(a[s])

while ok - no > 1:
    count = 0
    mid = (ok+no)//2
    for i in range(len(m)):
        if m[i] <= mid:
            count += 1
    if count >= k:
        ok = mid
    else:
        no = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  # (0, i]
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


def main():
    N = int(input())
    A = list(map(int, input().split()))

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        #if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        #if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        #if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])


def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a + 1)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


def main():
    N = int(input())
    A = list(map(int, input().split()))

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        #if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        #if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        #if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])


def solve(M):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a + 1)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


N = int(input())
A = list(map(int, input().split()))

# cnt = 0
# for i in range(N):
#     for j in range(i+1, N+1):
#         if sorted(A[i:j])[(j-i)//2] <= 5:
#             cnt += 1
#             print(i, j)
# print(cnt)

A_sorted = sorted(A)
ng, ok = -1, N-1
while ng + 1 < ok:
    c = (ng + ok) // 2
    M = A_sorted[c]
    if solve(M):
        ok = c
    else:
        ng = c
print(A_sorted[ok])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])


def solve(M):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = 2 * N
    bit = Bit(4*N)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a + 1)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


N = int(input())
A = list(map(int, input().split()))

# cnt = 0
# for i in range(N):
#     for j in range(i+1, N+1):
#         if sorted(A[i:j])[(j-i)//2] <= 5:
#             cnt += 1
#             print(i, j)
# print(cnt)

A_sorted = sorted(A)
ng, ok = -1, N-1
while ng + 1 < ok:
    c = (ng + ok) // 2
    M = A_sorted[c]
    if solve(M):
        ok = c
    else:
        ng = c
print(A_sorted[ok])