Submission #22354907

---

Source Code Expand

A = tuple(map(int, open(0).read().split()))[1:]

N = len(A)

def check(x):
  """
  (上側の) 中央値が x 以上なら True を返す。
  x 以上のものは +1、x 未満のものは -1 と数えて、区間和が 0 以上なら対象
  """
  N = len(A)
  count = [0] * (N + N + 10)
  count[0] = 1
  now = 0
  cumsum = 1
  k = 0
  for a in A:
    if a >= x:
      now += 1
      cumsum += count[now]
    else:
      cumsum -= count[now]
      now -= 1
    k += cumsum
    count[now] += 1
    cumsum += 1
  return k + k >= N * (N + 1) // 2

B = sorted(A)
# 中央値は B[i] 以上である
ok, ng = 0, N
while ok + 1 < ng:
  i = (ng + ok) // 2
  if check(B[i]):
    ok = i
  else:
    ng = i

print(B[ok])

Submission Info

Judge Result