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:
n = int(input())
A = list(map(int, input().split()))

# n = 4
# A = [i+1 for i in range(n)]

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

#print((n*(n+1))//(2*2))

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i+1] >= mid)
    bit = Bit(n+2)
    ans = 0
    for i in range(n):
        if S[i] >= 0:
            ans += 1

    #print("S OK")

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    #print("S OK2")
    #print(S)
    for i, p in enumerate(S):
        
        bit.add(p, 1)

        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く
        #print(i,ans)


    #print(le, ri, mid, ans)

    if ans >= (n*(n+1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)

Submission status: Accepted

Solution code:
def f(n, a):
    x = list(sorted(set(a)))
    n_sub_half = n * (n + 1) // 2 // 2
    n_plus_minus = n * 2 + 1
    Li = 0
    Ri = len(x)
    while Ri > Li + 1:
        i = (Li + Ri) // 2
        xi = x[i]
        cnt_sum = [0] * n_plus_minus
        cumsum = 0
        cnt_sum[cumsum] = 1
        judge = 0
        s = 0
        for ak in a:
            if ak >= xi:
                cumsum += 1
                s += cnt_sum[cumsum] + 1
            else:
                cumsum -= 1
                s -= cnt_sum[cumsum + 1] - 1
            cnt_sum[cumsum] += 1
            judge += s
            if judge >= n_sub_half:
                Li = i
                break
        else:
            Ri = i
    print(x[Li])

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import ceil

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
        
    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
        return ret
    
    def reset(self):
        self.bit = [0] * (self.n + 1)

ub = max(a) + 1
lb = 0
th = ceil(((N + 1) * N // 2) / 2)
bit = BIT(N + 1)

while ub - lb > 1:
    mid = (ub + lb) // 2
    b = [1 if v >= mid else -1 for v in a]
    b = [0] + list(accumulate(b))
    b_sorted = {v: i + 1 for i, v in enumerate(sorted(b))}
    
    # Count inversion
    cnt = 0
    bit.reset()
    for v in b:
        cnt += bit.query(b_sorted[v])
        bit.update(b_sorted[v], 1)
        
    if cnt >= th:
        lb = mid
    else:
        ub = mid
    
print(lb)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict

N = int(input())
A = np.array(input().split(), dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  # xより真に大きな値を1、他を-1とする。
  # 1の個数が-1の個数以上になっている区間
  current = 0 # 累積和
  memo = defaultdict(int) # 過去の累積和の分布, incl empty
  memo[0] = 1
  cnt_below = 1 # sum memo[y] for y <= x
  result = 0
  for a in A:
    if a > x:
      current += 1
      cnt_below += memo[current]
    else:
      cnt_below -= memo[current]
      current -= 1
    result += cnt_below
    memo[current] += 1
    cnt_below += 1
  return result <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)

Submission status: Accepted

Solution code:
def f(n, a):
    x = list(sorted(set(a)))
    n_sub_half = n * (n + 1) // 2 // 2
    n_plus_minus = n * 2 + 1
    Li = 0
    Ri = len(x)
    while Ri > Li + 1:
        i = (Li + Ri) // 2
        xi = x[i]
        cnt_sum = [0] * n_plus_minus
        cumsum = 0
        cnt_sum[cumsum] = 1
        judge = 0
        s = 0
        for ak in a:
            if ak >= xi:
                cumsum += 1
                s += cnt_sum[cumsum] + 1
            else:
                cumsum -= 1
                s -= cnt_sum[cumsum + 1] - 1
            cnt_sum[cumsum] += 1
            judge += s
            if judge >= n_sub_half:
                Li = i
                break
        else:
            Ri = i
    print(x[Li])


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

Submission status: Accepted

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()
# 区間の全組み合わせ(累積和配列N+1から2つ選ぶ組み合わせ)
ALL=(N+1)*N//2

# 転倒数の取得
def get_inv(A):
    N=len(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))
    # 区間の全組み合わせ - 累積和の転倒数(1より-1のが多かった区間の数)
    # = 中央値がX以上となる区間の数(1のが多いor同数だった区間の数)
    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: Accepted

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
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 4

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= comb else binsearch(lft, half)

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

Submission status: Accepted

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
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

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

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= comb // 2 else binsearch(lft, half)

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

Submission status: Accepted

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
    
    def reset(self):
        for i in range(len(self.tree)):
            self.tree[i] = 0

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

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= math.ceil(comb/2) else binsearch(lft, half)

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

Submission status: Accepted

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

Solution code:
def bisect_right_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以下となる、最も右の値 + 1
    bisect.bisect_right と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if x < fn(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


N = int(input())
series = list(map(int, input().split()))
series_sorted = sorted(series)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


def count_lr(x):
    """
    x 以上の数を半分以上含む == 中央値が x 以上である、L と r の選び方の数
    :param x:
    :return:
    """
    ret = 0
    # series[i] が x 未満なら 1、x 以上なら -1 を i番目に持つ配列の、i=0 から i までの累積和。
    cumsum = 0
    # counts[i]: cumsum が i に何回なったか
    counts = {i: 0 for i in range(-N, N + 1)}
    counts[cumsum] = 1
    diff = 0
    for i in range(N):
        if series[i] >= x:
            cumsum += 1
            counts[cumsum] += 1
            diff += counts[cumsum]
        else:
            cumsum -= 1
            counts[cumsum] += 1
            diff -= counts[cumsum + 1] - 1
        ret += diff
    return ret


# count_lr(x) の結果が半分以上であれば、中央値は x 以上。
# count_lr(x) が半分以上のうち一番大きい x を探す。
def solve(i):
    if count_lr(series_sorted[i]) >= (lr_size + 1) // 2:
        return 0
    else:
        return float('inf')


ans_i = bisect_right_callable(solve, 0, lo=0, hi=N)
print(series_sorted[max(0, min(N - 1, ans_i - 1))])

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


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

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)  # -N ~ +Nまで。0はN番目。
# にぶたん：「答えがX以上か？」
ok, ng = 0, 10 ** 9 + 1
while abs(ok - ng) > 1:
    X = (ok + ng) // 2

    B = [(1 if a >= X else - 1) for a in A]
    B = [0] + list(accumulate(B))

    cnt = 0
    BIT.reset()
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}
    for j, b in enumerate(B):
        cnt += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if cnt >= ceil((N * (N + 1)) // 2 / 2):
        ok = X
    else:
        ng = X

print(ok)

Submission status: Accepted

Solution code:
def d_median_of_medians(N, A):
    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

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

        def sum(self, index):
            """tree[1]からtree[index]までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """tree[index]にvalueを加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    def is_accepted(x):
        """
        A[l]からA[r]までの要素の中央値がx以上か。すなわち、A[l]からA[r]までの
        要素のうちx以上であるものが (N*(N+1)/2)/2 個以上か
        """
        from itertools import accumulate
        from math import ceil
        a_larger_x = [(1 if a >= x else -1) for a in A]  # x以上か否かを{1, -1}に変換
        cumsum = list(accumulate(a_larger_x))

        ans = 0
        a_larger_x_sorted = {a: k for k, a in enumerate(sorted(cumsum), 1)}
        bit = BIT(N)
        for c in cumsum:
            ans += bit.sum(a_larger_x_sorted[c]) + int(c >= 0)
            bit.add(a_larger_x_sorted[c], 1)
        return True if ans >= ceil((N * (N + 1)) / 4) else False

    # 二分探索の探索区間は [min(A), max(A)] で十分だが、
    # min, maxはO(N)なので、決め打ちしたほうがNが大きなとき速い
    accept = 0
    reject = 10**9 + 1  # 数列の要素の値の制約から、この値は中央値になりえない
    while reject - accept > 1:
        mid = (accept + reject) // 2
        if is_accepted(mid):
            accept = mid
        else:
            reject = mid
    return accept

N = int(input())
A = [int(i) for i in input().split()]
print(d_median_of_medians(N, A))

Submission status: Accepted

Solution code:
import math

n = int(input())
lst = list(map(int, input().split()))
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
            
def judge(x, lst, n):
 
    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    lst_accum = []
    a = 0
    for i in lst_r:
        a += i
        lst_accum.append(a)
    
    bit = Bit(n)
    lst_accum_sorted = {b: i for i, b in enumerate(sorted(lst_accum), start=1)}
    count = 0
    for j, b in enumerate(lst_accum):
        count += bit.sum(lst_accum_sorted[b]) + (b >= 0)
        bit.add(lst_accum_sorted[b], 1)
        
    if count >= math.ceil(all_pair/2):
        return True
    else:
        return False
 
    
sorted_lst = sorted(lst)
low = 0
high = len(lst) - 1
while high - low >1:
    t = (low+high) // 2
    i = sorted_lst[t]
    if judge(i, lst, n):
        low = t
    else:
        high = t
        
print(sorted_lst[high]) if judge(sorted_lst[high], lst, n) else print(sorted_lst[low])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import ceil

class BIT():
    def __init__(self,n):
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x):
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum(self,i):
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def reset(self):
        self.bit=[0]*(self.size+1)

n=int(input())
A=list(map(int,input().split()))
bit=BIT(n+1)
l,r=0,10**9+1
while r-l>1:
    mid=(l+r)//2
    B=[(1 if a>=mid else -1) for a in A]
    B=[0]+list(accumulate(B))
    cnt=0
    B_sorted={b: i for i,b in enumerate(sorted(B),start=1)}
    bit.reset()
    for b in B:
        cnt+=bit.sum(B_sorted[b])
        bit.add(B_sorted[b],1)
    if cnt>=ceil((n*(n+1)//2)/2):
        l=mid
    else:
        r=mid
print(l)

Submission status: Accepted

Solution code:
import math
 
n = int(input())
a = [int(i) for i in input().split(" ")]

m = n * (n + 1) // 2
 
class BIT:
    def __init__(self, n):
        self.t = [0] * (n + 1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= (i & -i)
        return s
    
    def add(self, i, v):
        while i < len(self.t):
            self.t[i] += v
            i += (i & -i)
            
def count(s):
    s_min = min(s)
    b = BIT(max(s) - s_min + 1)
    t = [0] * len(s)
    for j in range(0, len(s)):
        t[j] = b.sum(s[j] - s_min + 1)
        b.add(s[j] - s_min + 1, 1)
    return sum(t)
            
def bs(l, r):
    if l == r:
        return l
    else:
        h = math.ceil((l + r) / 2)
        
        ab = [-1 if a[i] < h else 1 for i in range(0, n)]
        s = [0] * (n + 1)
        
        for i in range(1, n + 1):
            s[i] = s[i - 1] + ab[i - 1]
            
        if count(s) >= math.ceil(m / 2):
            return bs(h, r)
        else:
            return bs(l, h - 1)
        
print(bs(min(a), max(a)))

Submission status: Accepted

Solution code:

def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)

Submission status: Accepted

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

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

alpha = sorted(a)
l, r = 0, n
m, c = n//2, n*(n+1)//2
while True:
    if check(alpha[m]) <= c//2:
        if m == n-1:
            break
        elif check(alpha[m+1]) > c//2:
            break
        else:
            l, m = m, (m+r)//2
    else:
        m, r = (m+l)//2, m+1
        
print(alpha[m])

Submission status: Accepted

Solution code:

from bisect import bisect_left
from math import ceil
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


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

    def __len__(self):
        return self.size

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

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(input())
a = [0] + [int(s) for s in input().split()]
# a = [0] * (N + 1)


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(set(s))
    ind = {v: i + 1 for i, v in enumerate(ss)}

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        j = ind[s[i]]
        count += b.sum(j)
        b.add(j, 1)

    return count


# i: 0, 1, ..., 10 ** 9
# x: 10 ** 9, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 - i), 10 ** 9 + 1)
ans = 10 ** 9 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

# 転倒数を求めるためのBIT
class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        while idx < self.size:
            self.bitree[idx] += val
            idx += idx&(-idx)
            
    def getsum(self, idx:int):
        ret = 0
        while idx > 0:
            ret += self.bitree[idx]
            idx -= idx&(-idx)
            
        return ret
    
    def reset(self):
        self.bitree = [0]*self.size
        
# 二分探索のための関数
def findInv(arr:list, med:int):
    arrbin = [-1 if ai < med else 1 for ai in arr]
    arrcum = [0] + list(accumulate(arrbin))
    arrcummin = abs(min(arrcum))
    arrcumpos = [arrcum_i + arrcummin + 1 for arrcum_i in arrcum]
    
    bitree = BIT(max(arrcumpos))
    inv = 0
    for i,ai in enumerate(arrcumpos):
        inv += (i - bitree.getsum(ai))
        bitree.addval(ai, 1)
        
    return inv

# 二分探索
def binsearch(arr:list):
    low = 0
    high = max(arr) + 1
    n = len(arr)
    threshould = n*(n+1)//4
    
    while high-low > 1:
        mid = (high+low) // 2

        if findInv(arr, mid) <= threshould:
            low = mid
            
        else:
            high = mid
            
    return low        

n = ni()
a = list(li())

print(binsearch(a))

Submission status: Accepted

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


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

    def add(self, k, x):
        while k < self.n:
            self.data[k] += x
            k += k & -k

    def get(self, k):
        s = 0
        while k > 0:
            s += self.data[k]
            k -= k & -k

        return s

    def init(self, n):
        self.n = n
        self.data = [0] * n


left, right = 0, 10 ** 9 + 5
bit = BIT(N)
while right - left > 1:
    x = (right + left) // 2

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    p = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += p
    q = max(S) + 1
    bit.init(q)
    num = 0
    for i in S:
        num += bit.get(i)
        bit.add(i, 1)

    if num * 2 >= N * (N + 1) // 2:
        left = x
    else:
        right = x

print(left)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
data = [0] * (N + 1)


def add(k, x, M):
    while k <= M:
        data[k] += x
        k += k & -k


def get(k):
    s = 0
    while k > 0:
        s += data[k]
        k -= k & -k

    return s


left, right = 0, 10 ** 9 + 1
while right - left > 1:
    x = (left + right) // 2

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    a = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += a

    b = max(S)
    data = [0] * (b + 1)
    num = 0
    for i in S:
        num += get(i)
        add(i, 1, b)

    if num * 2 >= (N * (N + 1) // 2):
        left = x
    else:
        right = x

print(left)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


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

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


ok, ng = 0, 10 ** 9 + 1
BIT = BinaryIndexedTree(N + 1)
while abs(ok - ng) > 1:
    X = (ok + ng) // 2
    B = [(1 if a >= X else -1) for a in A]
    B = [0] + list(accumulate(B))
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}

    tmp = 0
    BIT.reset()
    for j, b in enumerate(B):
        tmp += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if tmp >= ceil((N * (N + 1) / 2) / 2):
        ok = X
    else:
        ng = X

print(ok)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


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

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


lo, hi = -1, 10 ** 9 + 1
BIT = BinaryIndexedTree(N + 1)
while hi - lo > 1:
    X = (hi + lo) // 2
    B = [(1 if a >= X else -1) for a in A]
    B = [0] + list(accumulate(B))
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}

    tmp = 0
    BIT.reset()
    for j, b in enumerate(B):
        tmp += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if tmp >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X

print(lo)

Submission status: Accepted

Solution code:
def add(B,a,n):#リストに値を追加する関数
    x = a
    while x <= n:
        B[x] += 1
        x += x&(-x)

def sums(B,a):#a番目までの和
    x = a
    S = 0
    while x != 0:
        S += B[x]
        x -= x&(-x)
    return S


def invnumber(n, S):# #{(i,j)| i<j and S[i]<=S[j]}
    B = [0]*(n*2 + 1)
    invs = 0
    for i in range(n):
        s = S[i] + n
        invs += sums(B, s)
        add(B, s, n*2)
    return invs

N = int( input())
A = list( map( int, input().split()))
R = max(A)+1
L = 0
c = (N*(N+1)//2 + 1)//2
while R - L > 1:
    M = (R+L)//2
    S = [0]*(N+1)
    for i in range(1,N+1):
        if A[i-1] >= M:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(N+1,S) >= c:
        L = M
    else:
        R = M
print(L)