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:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1 ) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs) - 1

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            bit.add(s + n, 1)
            ret += bit.sum(s + n - 1)

        return ret

    while lo < hi:
        mid = (lo + hi) // 2
        if th < _f(xs[mid]):
            lo = mid + 1
        else:
            hi = mid
    return xs[lo]


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]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    th = N * (N + 1) // 4

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs) - 1

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            bit.add(s + n, 1)
            ret += bit.sum(s + n - 1)

        return ret

    while lo < hi:
        mid = (lo + hi) // 2
        if th < _f(xs[mid]):
            lo = mid + 1
        else:
            hi = mid
    return xs[lo]


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]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
lim=n*(n+1)//2//2
A=[int(i) for i in input().split()]
B=[]
D=collections.defaultdict(int)
if n%2==0:
  for i in range(n//2):
    D[A[i]]+=2*i+1
  for i in range(n//2):
    D[A[n//2+i]]+=n-2*i
else:
  for i in range(n//2+1):
    D[A[i]]+=2*i+1
  for i in range(n//2):
    D[A[n//2+i]]+=n-1-2*i
K=D.keys()
for k in K:
  B.append([k,D[k]])
B.sort(key=lambda x:x[0])
count=0
for i in range(len(set(A))):
  count+=B[i][1]
  if count>=lim:
    print(B[i][0])
    break

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = -1
Ri = len(x) - 1
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n - 1]
        else:
            s -= cnt_sum[cumsum + n]
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Ri])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N = int(input())
	A = input().split(" ")
	A = [int(s) for s in A]
	
	if N == 1:
		print(A[0])
		sys.exit()
	
	A.sort()
	AA = copy.deepcopy(A)
	#print(A)
	
	for i in range(N):
		if i == 0:
			continue
		if (i+1) % 2 == 0:
			AA = AA[1:]
			A += AA
			#print(AA)
		else:
			AA = AA[:-1]
			A += AA
			#print(AA)
	
	A.sort()
	tmp = (len(A) // 2) + 1
	#print(A)
	print(A[tmp])
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)

    # [0, i]の区間和
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

N=INT()
A=LIST()
# 区間の全組み合わせ
ALL=N*(N-1)//2

# 転倒数の取得
def get_inv(A):
    # マイナスの値を考慮するため今回は*2する
    bit=BIT(N*2+1)
    ans=0
    for i in range(N-1, -1, -1):
        bit.add(A[i]+N, 1)
        # 自分より右にある、自分より小さな数の個数
        ans+=bit.sum(A[i]+N-1)
    return ans

def calc(X):
    # X以上かどうかで1と-1にする配列L
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    # 累積和
    sm=list(accumulate(L))
    # 全組み合わせ - 累積和の転倒数
    ans=ALL-get_inv(sm)
    # 中央値がX以上となる区間が、全体の半分(切り上げ)以上あるかどうか
    return ans>=ceil(ALL, 2)

# 二分探索
A2=sorted(set(A))
low=0
hi=len(A2)
while low+1<hi:
    mid=(hi+low)//2
    if calc(A2[mid]):
        low=mid
    else:
        hi=mid
# 今回は境界の下が欲しいのでlowを出力
print(A2[low])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)

    # [0, i]の区間和
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

N=INT()
A=LIST()
# 区間の全組み合わせ
ALL=N*(N-1)//2

# 転倒数の取得
def get_inv(A):
    # マイナスの値を考慮するため今回は*2する
    bit=BIT(N*2+1)
    bit.add(N, 1)
    ans=0
    for i in range(N-1, -1, -1):
        bit.add(A[i]+N, 1)
        # 自分より右にある、自分より小さな数の個数
        ans+=bit.sum(A[i]+N-1)
    return ans

def calc(X):
    # X以上かどうかで1と-1にする配列L
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    # 累積和
    sm=[0]+list(accumulate(L))
    # 全組み合わせ - 累積和の転倒数
    ans=ALL-get_inv(sm)
    # 中央値がX以上となる区間が、全体の半分(切り上げ)以上あるかどうか
    return ans>=ceil(ALL, 2)

# 二分探索
A2=sorted(set(A))
low=0
hi=len(A2)
while low+1<hi:
    mid=(hi+low)//2
    if calc(A2[mid]):
        low=mid
    else:
        hi=mid
# 今回は境界の下が欲しいのでlowを出力
print(A2[low])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)

    # [0, i]の区間和
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

N=INT()
A=LIST()
# 区間の全組み合わせ
ALL=N*(N-1)//2

# 転倒数の取得
def get_inv(A):
    # マイナスの値を考慮するため今回は*2する
    bit=BIT(N*2+1)
    ans=0
    for i in range(N-1, -1, -1):
        bit.add(A[i]+N, 1)
        # 自分より右にある、自分より小さな数の個数
        ans+=bit.sum(A[i]+N-1)
    return ans

def calc(X):
    # X以上かどうかで1と-1にする配列L
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    # 累積和
    sm=[0]+list(accumulate(L))
    # 全組み合わせ - 累積和の転倒数
    ans=ALL-get_inv(sm)
    # 中央値がX以上となる区間が、全体の半分(切り上げ)以上あるかどうか
    return ans>=ceil(ALL, 2)

# 二分探索
A2=sorted(set(A))
low=0
hi=len(A2)
while low+1<hi:
    mid=(hi+low)//2
    if calc(A2[mid]):
        low=mid
    else:
        hi=mid
# 今回は境界の下が欲しいのでlowを出力
print(A2[low])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)

    # [0, i]の区間和
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

N=INT()
A=LIST()
# 区間の全組み合わせ
ALL=N*(N-1)//2

# 転倒数の取得
def get_inv(A):
    # マイナスの値を考慮するため今回は*2する
    bit=BIT(N*2+1)
    ans=0
    for i in range(N-1, -1, -1):
        bit.add(A[i]+N, 1)
        # 自分より右にある、自分より小さな数の個数
        ans+=bit.sum(A[i]+N-1)
    return ans

def calc(X):
    # X以上かどうかで1と-1にする配列L
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    # 累積和
    sm=[0]+list(accumulate(L))
    # 全組み合わせ - 累積和の転倒数
    ans=ALL-get_inv(sm)
    # 中央値がX以上となる区間が、全体の半分以上あるかどうか
    return ans>=ALL//2

# 二分探索
A2=sorted(set(A))
low=0
hi=len(A2)
while low+1<hi:
    mid=(hi+low)//2
    if calc(A2[mid]):
        low=mid
    else:
        hi=mid
# 今回は境界の下が欲しいのでlowを出力
print(A2[low])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)

    # [0, i]の区間和
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

N=INT()
A=LIST()
# 区間の全組み合わせ
ALL=N*(N-1)//2

# 転倒数の取得
def get_inv(A):
    # マイナスの値を考慮するため今回は*2する
    bit=BIT(N*2+1)
    ans=0
    for i in range(N-1, -1, -1):
        bit.add(A[i]+N, 1)
        # 自分より右にある、自分より小さな数の個数
        ans+=bit.sum(A[i]+N-1)
    return ans

def calc(X):
    # X以上かどうかで1と-1にする配列L
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    # 累積和
    sm=[0]+list(accumulate(L))
    # 全組み合わせ - 累積和の転倒数
    ans=ALL-get_inv(sm)
    # 中央値がX以上となる区間が、全体の半分以上あるかどうか
    return ans>=ALL//2

# 二分探索
A2=sorted(set(A))
low=-1
hi=len(A2)
while low+1<hi:
    mid=(hi+low)//2
    if calc(A2[mid]):
        low=mid
    else:
        hi=mid
# 今回は境界の下が欲しいのでlowを出力
print(A2[low])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
print(sorted_in)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} half {} value {}".format(lft, rgt, half, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    bit.add(N, 1)
    for i, x in enumerate(inarr):
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        # print("summed: {}, bit: {}".format(summed, bit.sum(N + summed)))
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print("num {} cnt {} judge {}".format(sorted_in[half], res, math.ceil(comb/2)))
    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res > math.ceil(comb/2):
        return binsearch(lft, half)
    else:
        return binsearch(half, rgt)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res >= math.ceil(comb/2):
        return binsearch(lft, half)
    else:
        return binsearch(half, rgt)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res >= math.ceil(comb/2):
        return binsearch(lft, half)
    else:
        return binsearch(half, rgt)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res >= math.ceil(comb/2):
        return binsearch(lft, half)
    else:
        return binsearch(half, rgt)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res <= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res < math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

Solution code:
import math
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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res < math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} value {}".format(lft, rgt, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res < (comb // 2 + 1):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print(lft, rgt, sorted_in[half])
    if lft >= half:
        return lft
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res < (comb // 2 + 1):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print(lft, rgt, sorted_in[half])
    if lft >= half:
        return lft
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, i - bit: {}, bit: {}".format(summed, i - bit.sum(N + summed), bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res <= (comb // 2 + 1):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])

Submission status: Wrong Answer

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print(lft, rgt, sorted_in[half])
    if lft >= half:
        return lft
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, x in enumerate(inarr):
        value = -1 if x < sorted_in[half] else 1
        summed += value
        # print("summed: {}, bit: {}".format(summed, i - bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res <= (comb // 2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])