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: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	#aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

	S = [0] #S_0 = 0を忘れずにつける
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	#S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
	#MIN = 0 , MAX = 6

	L = (MAX-MIN+1) #BITのサイズ L=6
	bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) #S_iの最小値が1となるように調整

		#BITで既出の要素のうちS_i以下の要素数をカウント
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		#BITのS_iに1を加算して更新
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans #中央値がx以上となる(l,r)の組の数

border = ( (N+1)*N//2 +1 )//2
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2

def ok(x):
    B = [0] * (2 * N + 1)
    res, cum, cur = 0, 0, 0
    B[0] += 1
    for a in A:
        if a >= x:
            cum += 1
            cur += B[cum]+1
        else:
            cur -= B[cum]-1
            cum -= 1
        B[cum] += 1
        res += cur
    return res >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(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 bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
A = list(map(int, readline().split()))
A2, C = compress(A)
A = [C[a] for a in A]
ok = 0
ng = max(A)+1
T = BIT(ng)
ma = min(A)+1
while abs(ok-ng) > 1:
    med = (ok+ng)//2
    B = [1 if a >= med else -1 for a in A]
    for i in range(1, N):
        B[i] += B[i-1]
    
    
    mb = -min(0, min(B))+1
    T = BIT(max(B)+mb)
    T.add(mb, 1)
    res = 0
    for b in B:
        res += T.get(mb+b)
        T.add(mb+b, 1)
    if res >= N*(N+1)//4:
        ok = med
    else:
        ng = med
print(A2[ok])

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.n + 1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
N = int(input())
A = list(map(int, input().split()))
N0 = N*(N+1)//2
def C(x):
    B = BIT(N*2+1)
    s = [0]*(N+1)
    for i in range(N):
        a = A[i]
        s[i] = 1 if x<a else -1
        s[i]+=s[i-1]
    res = 0
    for i in range(-1, N):
        res+=B.sum(s[i]+N+1)
        B.add(s[i]+N+1, 1)
    return res<N0//2
ok = max(A)
ng = min(A)-1
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if C(mid):#midが条件を満たすか
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import sys

def bit_add(iii,x):
    while iii<len(bit):
        bit[iii]+=x
        iii+=iii&(-iii)
def bit_sum(jjj):
    s=0
    while jjj>0:
        s+=bit[jjj]
        jjj-=jjj&(-jjj)
    return s

n=int(input())
a=list(map(int,input().split()))
num=n*(n+1)//2
high=max(a)
low=min(a)
while high-low>1:
    mid=(high+low)//2
    ans=0
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
        else:
            b.append(-1)
    for i in range(1,n):
        b[i]+=b[i-1]
    for i in range(n):
        b[i]+=n
    bit=[0]*(2*n+3)
    bit_add(n,1)
    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)
    if num%2==1:
        if ans>=num//2+1:
            low=mid
        else:
            high=mid
    else:
        if ans>=num//2:
            low=mid
        else:
            high=mid

            
            
if not high in a:
    print(low)
    sys.exit()
else:
    mid=high
    ans=0
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
        else:
            b.append(-1)
    for i in range(1,n):
        b[i]+=b[i-1]
    for i in range(n):
        b[i]+=n
    bit=[0]*(2*n+3)
    bit_add(n,1)
    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)
    if num%2==1:
        if ans>=num//2+1:
            print(high)
        else:
            print(low)
    else:
        if ans>=num//2:
            print(high)
        else:
            print(low)

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
 
    B = sorted(A)
    l, r = 0, N
    m, c = N // 2, N * (N + 1) // 2
 
    def check(x):
        b, r, y = N, 0, 0
        D = [0] * (2 * N + 1)
        for a in A:
            D[b] += 1
            if a < x:
                r += D[b]
                b += 1
            else:
                b -= 1
                r -= D[b]
            y += r
        return y
 
    while True:
        if check(B[m]) <= c // 2:
            if m == N - 1 or check(B[m + 1]) > c // 2:
                break
            else:
                l, m = m, (m + r) // 2
        else:
            m, r = (m + l) // 2, m + 1
 
    print(B[m])
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot=lambda x,y:x+y,e=0,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    M=max(A)

    def check(x):
        B=[1 if(a>=x) else -1 for a in A]
        S=[0]*(n+1)
        for i in range(n):
            S[i+1]=S[i]+B[i]

        D={d:i for i,d in enumerate(sorted(set(S)))}
        for i in range(n+1):
            S[i]=D[S[i]]

        cnt=0
        bit=BIT([0]*(n+1))
        for i in range(n+1):
            cnt+=bit.sum(S[i]+1)
            bit.add(S[i])

        return cnt*2>=n*(n+1)//2

    print(bisection(0,M,check))
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size

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

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res



n = I()
A = LI()



def D(L):
    n = len(L)
    bit = BIT(2 * n + 1)
    ans = 0
    for i in range(n - 1, -1, -1):
        bit.add(L[i] + n, 1)
        ans += bit.sum(L[i] + n - 1)
    return ans



ALL = (n + 1) * n // 2
A2 = sorted(A)
# 求めるのは、1より-1の方が多かった区間の数
ng, ok = n, 0
while ng > ok + 1:
    mid = (ok + ng) // 2
    L = [0] + list(accumulate([1 if i >= A2[mid] else -1 for i in A]))
    if D(L) >= ALL // 2 + 1:
        ng = mid
    else:
        ok = mid


print(A2[ok])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]

def binarysearch(ok,ng,isOK): #二分探索
    while(abs(ok-ng) > 1):
        mid = (ok + ng)//2
        if isOK(mid): ok = mid
        else: ng = mid
    return ok

from collections import Counter
def isOK(x): #中央値はx以上？
    c = [1 if i >= x else -1 for i in a]
    res = Counter([0])
    now = 0
    less = 1
    ans = 0
    for i in range(n):
        if c[i] > 0:
            less += res[now+1]
        else:
            less -= res[now]
        now += c[i]
        ans += less
        less += 1
        res[now] += 1
    return ans >= (n*(n+1)//2+1)//2      


ans = binarysearch(0,10**9+1,isOK)
print(ans)

Submission status: Accepted

Solution code:
NN = 18
N = int(input())
A = [int(a) for a in input().split()]

def chk(k):
    s = 0
    c = 0
    BIT=[0]*(2**NN+1)
    def add(i, x=1):
        i += 1 << NN - 1
        while i <= 2**NN:
            BIT[i] += x
            i += i & (-i)

    def getsum(i):
        ret = 0
        i += 1 << NN - 1
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    add(0)
    for i in range(N):
        if A[i] >= k:
            s += 1
        else:
            s -= 1
        c += getsum(s)
        add(s)
    if 4 * c >= N * (N+1):
        return 1
    return 0

l, r = 0, 1<<30
while r - l > 1:
    m = (l+r) // 2
    if chk(m):
        l = m
    else:
        r = m
print(l)

Submission status: Accepted

Solution code:
from itertools import accumulate

class BIT_RSQ():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, v):
        while i <= self.n:
            self.data[i-1] += v
            i += i & -i

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

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

def check(m):
    b = [[-1,1][i>=m] for i in a]
    bit = BIT_RSQ(2*n+1)
    s = [0] + list(accumulate(b))
    res = 0
    for i in range(n):
        bit.add(s[i]+n+1, 1)
        res += bit.sum(s[i+1]+n+1)
    return res >= (n*(n+1)//2+1)//2

left = 0
right = 10**9+1
while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        left = mid
    else:
        right = mid
print(left)

Submission status: Accepted

Solution code:
from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cmin = min(C)
    for i in range(N+1):
        C[i] -= cmin  # offset
    cmax = max(C)+1
    fw = FenwickTree(cmax)
    cnt = 0
    for i in range(N+1):
        cnt += fw.sum(C[i])
        fw.add(C[i], 1)

    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(i) for i in input().split()]

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

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

def check(x) :
    b = [0] + [1 if a[i] >= x else -1 for i in range(N)]
    for i in range(1, N + 1) :
        b[i] += b[i-1]
    BIT = BinaryIndexedTree(2*N+2)
    
    ret = 0
    for i in range(N+1) :
        ret += BIT.sum(N+1+b[i])
        BIT.add(N+1+b[i], 1)
    
    return ret >= half
    
aa = sorted(a)
ok = 0
ng = N
while ng - ok > 1 :
    mid = (ok + ng) // 2
    if check(aa[mid]) :
        ok = mid
    else :
        ng = mid

print(aa[ok])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


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 inversion(a):
    "転倒していない組(l, r)の個数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        ans += b.sum(d[av])
        b.add(d[av], 1)
    return ans


def solve(N: int, a: "List[int]"):

    def isOK(y):
        acc = (1 if aa >= y else -1 for aa in a)
        acc = tuple([0]) + tuple(accumulate(acc))
        invs = inversion(acc)
        if acc[0] == -1:
            invs -= 1
        return invs < (N*(N+1))//4

    def binary_search(x):

        ng = -1
        ok = len(x)+1

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

    ng, ok = binary_search(range(max(a)))
    print(ng)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1 = 0
        i2 = 0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt
 
 
n = int(input())
l = [int(_) for _ in input().split()]
p = (n*n+n)/2
q = 0
if p%2 == 0:
    q = p//2
else:
    q = p//2 + 1
l_set = list(set(l))
l_sorted = sorted(l_set)
ans = 0
l_t = [0 for _ in range(n)]
s = [0 for _ in range(n+1)]
 
low = 0
high = len(l_sorted) - 1
 
 
while low <= high:
    mid = (low + high) // 2
    m = l_sorted[mid]
    for j in range(n):
        if l[j] < m:
            l_t[j] = -1
        else:
            l_t[j] = 1
    for k in range(n):
        s[k+1] = s[k] + l_t[k]
 
    x = mergecount(s)
    if p-x >= q:
        low = mid+1
        ans = max(m,ans)
    else:
        high = mid-1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size

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

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



def D(L):
    n = len(L)
    bit = BIT(2 * n + 1)
    ans = 0
    for i in range(n - 1, -1, -1):
        bit.add(L[i] + n, 1)
        ans += bit.sum(L[i] + n - 1)
    return ans



ALL = (n + 1) * n // 2
A2 = sorted(A)
# 求めるのは、1より-1の方が多かった区間の数
ng, ok = n, 0
while ng > ok + 1:
    mid = (ok + ng) // 2
    L = [0] + list(accumulate([1 if i >= A2[mid] else -1 for i in A]))
    if D(L) >= ALL // 2 + 1:
        ng = mid
    else:
        ok = mid


print(A2[ok])

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())

    B = sorted(A)
    l, r = 0, N
    m, c = N // 2, N * (N + 1) // 2

    def check(x):
        b, r, y = N, 0, 0
        D = [0] * (2 * N + 1)
        for a in A:
            D[b] += 1
            if a < x:
                r += D[b]
                b += 1
            else:
                b -= 1
                r -= D[b]
            y += r
        return y

    while True:
        if check(B[m]) <= c // 2:
            if m == N - 1 or check(B[m + 1]) > c // 2:
                break
            else:
                l, m = m, (m + r) // 2
        else:
            m, r = (m + l) // 2, m + 1

    print(B[m])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())

    B = sorted(A)
    l, r = 0, N
    m, c = N // 2, N * (N + 1) // 2

    def check(x):
        b, r, y = N, 0, 0
        D = [0] * (2 * N + 1)
        for a in A:
            D[b] += 1
            if a < x:
                r += D[b]
                b += 1
            else:
                b -= 1
                r -= D[b]
            y += r
        return y

    while True:
        if check(B[m]) <= c // 2:
            if m == N - 1 or check(B[m + 1]) > c // 2:
                break
            l, m = m, (m + r) // 2
        else:
            m, r = (m + l) // 2, m + 1

    print(B[m])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, i = LI()
    print(n-i+1)
    return

#B
def B():
    h, w = LI()
    a = SR(h)
    dy = defaultdict(int)
    dx = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == "#":
                dx[x] = 1
                dy[y] = 1
    dy = list(sorted(dy.items(), key=lambda x: x[0]))
    dx = list(sorted(dx.items(), key=lambda x: x[0]))
    for y,_ in dy:
        for x,_ in dx:
            print(a[y][x], end="")
        print()
    return

#C
def C():
    n, k = LI()
    x = LI()
    ans = inf
    for i in range(n - k + 1):
        if x[i] * x[i + k - 1] > 0:
            ans = min(ans, max(abs(x[i]), abs(x[i + k - 1])))
            continue
        ans = min(ans, min(abs(x[i]), abs(x[i + k - 1])) * 2 + max(abs(x[i]), abs(x[i + k - 1])))
    print(ans)
    return

# D 
# 解説AC
# 転倒数を求める BIT(BinaryIndexedTree) は主な問題ではないので説明は省く
# 転倒数を求めるのに至るまでの考察がきもい
# 工夫したリストの転倒数を求めることで
# 各値が何個の範囲 [l,r] の中央値として存在するかを求められる
#
# 1) 工夫したリスト
# 今回必要なのはある番目において
# a[i] より小さい数が何個あって a[i] より大きい数が何個あるかという情報
# 特に a[i] より(大きい数-小さい数)の情報が欲しい
# 典型として覚えるなら、 a[k] < a[i] で 1 、 a[k] >= a[i] で-1
# として累積和とるとa[k]までの(大きい数-小さい数)が求められる
#  
# 2) 中央値の性質 
# 長さ M の整数列 b の中央値を x として
# • b 中に x 以上の要素が ⌈M/2⌉以上含まれる
# • x は，上の性質を満たす整数の中で最大である
# が中央値の性質になり、つまり2分探索で求められることがわかる
#
# 3) 問題の言いかえ
# つまり問題は
# a の連続部分列 a[l, r] (1 ≤ l ≤ r ≤ N) のうち
# x 以上の要素を ⌈r−l+1/2⌉ 個以上含むものは何通り(x通り)で、
# (n+1)*n//2 - x 通りが (n+1)*n//2 の半分より多い（要は全連続部分列において
# x以上の数がその連続列の半数以上である物の数が全連続部分文字列の半分より多い）
# ならそれは全中央値の中央値としてなりえて、この性質を満たす最大値が答えになる  
# と言い換えることができる
# 各連続部分文字列の中央値をmとしてそれにおいて x 以上の要素がその連続列の半数以上である場合
# x は中央値以下であり中央値のリストを作った際 x はその部分列の中央値としてリストに入れられた
# もの以下になるため 中央値のリストの中央値を求める際の x が中央値のリストの中央値になるかの判定
# においてその部分の中央値の値は x よりも大きいため x 以上の要素数に 1 加えることができる
# この x 以上の要素がその連続列の半数以上である場合という部分において、工夫したリストは
#  S[i] =　i_∑_j=1 {ai}となっているため a[l, r] の要素の総和は S_r − S_{l−1}となっていて
# (l, r) (0 ≤ l < r ≤ N) のうち，Sl ≤ Sr を満たすものを数えると x 以上の要素が含まれる数
# がその列の半数を超えるものの数を数えていることと同じになり、つまりこれは転倒数を求めることで求められる
#
# 注意)
# なお転倒数は負の数があると難しいのでx以下の数はどう数えてもn以上にならないためnを足すことで-1*n
# を帳消ししている
def D():
    class BinaryIndexedTree:
        # http://hos.ac/slides/20140319_bit.pdf
        def __init__(self, size):
            """
            :param int size:
            """
            self.bit = [0 for _ in range(size)]
            self.size = size

        def add(self, i, w):
            """
            i番目にwを加える
            :param int i:
            :param int w:
            :return:
            """
            x = i + 1
            while x <= self.size:
                self.bit[x - 1] += w
                x += x & -x
            return

        def sum(self, i):
            """
            [0,i]の合計
            :param int i:
            :return:
            """
            res = 0
            x = i + 1
            while x > 0:
                res += self.bit[x - 1]
                x -= x & -x
            return res

        def __len__(self):
            return self.size
            
    def count_inversions(array, Max=None):
        """
        リストから転倒数 (array[i] > array[j] (i < j) となる (i, j) の組み合わせ数) を返す
        バブルソートするときに反転する必要がある数。
        :param list of int array:
                すべての要素が 0 以上の int である配列。
        :param int max: array の最大値。指定はわかる場合
        :rtype: int
        """
        if not Max:
            Max = max(array) + n
        bit = BinaryIndexedTree(Max + 1)
        res = 0
        for i in range(len(array)):
            res += i - bit.sum(array[i])
            bit.add(array[i], 1)
        return res

    def f(i):
        x = a_sorted[i]
        c = [n] + [1 if e >= x else - 1 for e in a]
        for i in range(n):
            c[i + 1] += c[i]
        tmp = count_inversions(c, 2 * n)
        if invmax - tmp >= (invmax + 1) // 2:
            return True
        else:
            return False
        
        
        
    
    n = II()
    a = LI()
    a_sorted = sorted(a)
    invmax = (n + 1) * n // 2

    ok = 0
    ng = n
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(a_sorted[ok])
    return
#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, i = LI()
    print(n-i+1)
    return

#B
def B():
    h, w = LI()
    a = SR(h)
    dy = defaultdict(int)
    dx = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == "#":
                dx[x] = 1
                dy[y] = 1
    dy = list(sorted(dy.items(), key=lambda x: x[0]))
    dx = list(sorted(dx.items(), key=lambda x: x[0]))
    for y,_ in dy:
        for x,_ in dx:
            print(a[y][x], end="")
        print()
    return

#C
def C():
    n, k = LI()
    x = LI()
    ans = inf
    for i in range(n - k + 1):
        if x[i] * x[i + k - 1] > 0:
            ans = min(ans, max(abs(x[i]), abs(x[i + k - 1])))
            continue
        ans = min(ans, min(abs(x[i]), abs(x[i + k - 1])) * 2 + max(abs(x[i]), abs(x[i + k - 1])))
    print(ans)
    return

# D
# 解説AC
def D():
    class BinaBinaryIndexedTree:
        # http://hos.ac/slides/20140319_bit.pdf
        def __init__(self, size):
            """
            :param int size:
            """
            self.bit = [0 for _ in range(size)]
            self.size = size

        def add(self, i, w):
            """
            i番目にwを加える
            :param int i:
            :param int w:
            :return:
            """
            x = i + 1
            while x <= self.size:
                self.bit[x - 1] += w
                x += x & -x
            return

        def sum(self, i):
            """
            [0,i]の合計
            :param int i:
            :return:
            """
            res = 0
            x = i + 1
            while x > 0:
                res += self.bit[x - 1]
                x -= x & -x
            return res

        def __len__(self):
            return self.size 

    def count_inversions(array, Max=None):
        """
        リストから転倒数 (array[i] > array[j] (i < j) となる (i, j) の組み合わせ数) を返す
        バブルソートするときに反転する必要がある数。
        :param list of int array:
                すべての要素が 0 以上の int である配列。
        :param int max: array の最大値。指定はわかる場合
        :rtype: int
        """
        if not Max:
            Max = max(array) + n
        bit = BinaBinaryIndexedTree(Max + 1)
        res = 0
        for i in range(len(array)):
            res += i - bit.sum(array[i])
            bit.add(array[i], 1)
        return res

    def f(i):
        x = a_sorted[i]
        c = [n] + [1 if e >= x else - 1 for e in a]
        for i in range(n):
            c[i + 1] += c[i]
        tmp = count_inversions(c, 2 * n)
        if invmax - tmp >= (invmax + 1) // 2:
            return True
        else:
            return False
        
        
        
    
    n = II()
    a = LI()
    a_sorted = sorted(a)
    invmax = (n + 1) * n // 2

    ok = 0
    ng = n
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(a_sorted[ok])
    return
#Solve
if __name__ == '__main__':
    D()