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: Time Limit Exceeded

Solution code:
import math
from statistics import median_high as med

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

medians = []
for i in range(N + 1):
    for j in range(i+1, N + 1):
        medians.append(med(A[i:j]))

print(med(medians))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
t = []
if n > 1:
    for i in range(n - 1):
        for j in range(i + 1, n):
            if (j - i) % 2 == 0:
                t.append(sorted(a[i:j+1])[((j-i)//2)])
            else:
                t.append(sorted(a[i:j+1])[((j-i)//2)+1])
    len_t = len(t)
    t.sort()
    if len_t % 2 == 0:
        print(t[len_t // 2])
    else:
        print(t[(len_t // 2) + 1])
else:
    print(a[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
med = lambda x : sorted(x)[len(x)//2]
m = [med(a[i:j]) for i in range(n) for j in range(i+1, n+1)]
print(med(m))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = 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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = 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 self.size >= 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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = []
    for p in a:
        s.add((p >= x) + 1, 1)
        S.append(s.tree[2] - 2 * s.tree[1])
    judge = 0
    bit = Bit(n)
    w = abs(min(S)) + 1
    for p in S:
        bit.add(p + w, 1)
        judge += bit.sum(p + w)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = 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 self.size >= 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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = []
    for p in a:
        s.add((p >= x) + 1, 1)
        S.append(s.tree[2] - 2 * s.tree[1])
    ret = 0
    bit = Bit(n)
    w = abs(min(S)) + 1
    for p in S:
        bit.add(p + w, 1)
        ret += bit.sum(p + w)
    return ret
 
 
b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]) >= n_sub_half:  # ans >= x
        if m == len(b) - 1:
            break
        elif f(b[m + 1]) < n_sub_half:
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1
 
 
print(b[m])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = 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 self.size >= 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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = []
    for p in a:
        s.add((p >= x) + 1, 1)
        S.append(s.tree[2] - 2 * s.tree[1])
    ret = 0
    bit = Bit(n)
    w = abs(min(S)) + 1
    for p in S:
        bit.add(p + w, 1)
        ret += bit.sum(p + w)
    return ret


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]) >= n_sub_half:  # ans >= x
        if m == len(b) - 1:
            break
        elif f(b[m + 1]) < n_sub_half:
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = 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 self.size >= 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 f(x):# 連続部分列の中央値がｘなる場合の数
    s = np.array([0] * (n + 1))
    for i, ai in enumerate(a):# 累積和ｓ
        if ai >= x:
            s[i + 1:] += 1
        else:
            s[i + 1:] -= 1
    s[:] += abs(np.min(s)) + 1
    ret = 0
    bit = Bit(n)
    for p in s[1:]:
        bit.add(p, 1)
        ret += bit.sum(p)
    return ret


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]) >= n_sub_half:  # ans >= x
        if m == len(b) - 1:
            break
        elif f(b[m + 1]) < n_sub_half:
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))

def f(x):# 連続部分列の中央値がｘなる場合の数
    s = np.array([0] * (n + 1))
    for i, ai in enumerate(a):# 累積和ｓ
        if ai >= x:
            s[i + 1:] += 1
        else:
            s[i + 1:] -= 1
    ret = 0
    BIT = np.array([0] * (2 * n + 1))
    for j in range(1, n + 1):
        BIT[n + s[j]] += 1
        ret += np.sum(BIT[:n + s[j] + 1])
    return ret


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]) >= n_sub_half:  # ans >= x
        if m == len(b) - 1:
            break
        elif f(b[m + 1]) < n_sub_half:
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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個以下」
  B = (((A > x) * 2) - 1).cumsum()
  B -= B.min() - 1
  L = B.max() + 1
  BIT = [0]*L
  cnt = 0
  
  for b in [1] + list(B):
    x = b
    while x:
      cnt += BIT[x]
      x -= (x & (-x))
    x = b
    while x < L:
      BIT[x] += 1
      x += (x & (-x))
  return cnt <= (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: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a > x else -1))
  m = min(B)-1
  L = max(B)-m+1
  BIT = [0]*L
  cnt = 0
  for b in B:
    x = b-m
    while x:
      cnt += BIT[x]
      x -= (x & (-x))
    x = b-m
    while x < L:
      BIT[x] += 1
      x += (x & (-x))
  return cnt <= (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: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    x += (x & (-x))
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    x -= (x & (-x))
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a > x else -1))
  m = min(B)-1
  BIT = [0]*(N+1)
  cnt = 0
  prev = 1
  for b in B[1:N+1]:
    b -= m
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,b) # 右端がRとなる(L,R)対
    prev = b
    
  return cnt <= (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: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    x += (x & (-x))
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    x -= (x & (-x))
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a > x else -1))
  m = min(B)-1
  B = [x-m for x in B]
  BIT = [0]*(N+1)
  cnt = 0
  prev = 1
  for b in B[1:N+1]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,b) # 右端がRとなる(L,R)対
    prev = b
    
  return cnt <= (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: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))


def f(x):# 連続部分列の中央値がｘなる場合の数
    s = np.array([0] * (n + 1))
    for i, ai in enumerate(a):# 累積和ｓ
        if ai >= x:
            s[i + 1:] += 1
        else:
            s[i + 1:] -= 1
    c = 0
    for L in range(1, n + 1):
        for R in range(L, n + 1):
            if s[R] >= s[L]:
                c += 1
    return c


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]) >= n_sub_half:  # ans >= x
        if m == len(b) - 1:
            break
        elif f(b[m + 1]) < n_sub_half:
            break
        else:
            l = m
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (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: Time Limit Exceeded

Solution code:
import numpy as np
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 BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],((A > x).astype(int)*2-1).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  B -= np.min(B) - 1
  M = B.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (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: Time Limit Exceeded

Solution code:
import numpy as np
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 BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],((A > x).astype(int)*2-1).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  B -= np.min(B) - 1
  M = B.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

left = 0 # 答はleftより大きいである
right = 10**9 # 答はright以下である
while right - left > 1:
  mid = (left+right)//2
  if test(mid):
    right = mid
  else:
    left = mid
    
answer = right
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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 BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],(A > x).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  C = 2*B-np.arange(N+1)
  C -= np.min(C) - 1
  M = C.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  prev = C[0]
  for c in C[1:]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,c) # 右端がRとなる(L,R)対
    prev = c
  return cnt <= (total_medians-1)//2

AA = sorted(set(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: Time Limit Exceeded

Solution code:
import numpy as np
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 BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],(A > x).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  C = 2*B-np.arange(N+1)
  C -= np.min(C) - 1
  M = C.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  prev = C[0]
  for c in C[1:]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,c) # 右端がRとなる(L,R)対
    prev = c
  return cnt <= (total_medians-1)//2

left = 0 # 答はleftより大きいである
right = 10**9 # 答はright以下である
while right - left > 1:
  mid = (left+right)//2
  if test(mid):
    right = mid
  else:
    left = mid
    
answer = right
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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 BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],(A > x).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  C = 2*B-np.arange(N+1)
  C -= np.min(C) - 1
  M = C.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,C[R-1],1)
    cnt += BIT_sum(BIT,C[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

left = 0 # 答はleftより大きいである
right = 10**9 # 答はright以下である
while right - left > 1:
  mid = (left+right)//2
  if test(mid):
    right = mid
  else:
    left = mid
    
answer = right
print(answer)

Submission status: Time Limit Exceeded

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)

    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:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        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: Time Limit Exceeded

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 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)



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: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
B=[]
for i in range((n-1)//2+1):
  for j in range(i*2+1):
    B.append(A[i])
for i in range(n//2):
  for j in range(n//2*2-2*i):
    B.append(A[i])
B.sort()
print(B[len(B)//2])

Submission status: Time Limit Exceeded

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

f = lambda a: sorted(a)[len(a)//2]
m = a[:] + [f(a[i:i+r]) for r in range(2, n) for i in range(n-r+1)]

print(f(m))

Submission status: Time Limit Exceeded

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
    tmp = 0
    for uk in UorD:
        cumsum += uk
        cnt_sum[cumsum + n] += 1
        tmp += sum(cnt_sum[:cumsum + n])
        if tmp >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Ri])

Submission status: Time Limit Exceeded

Solution code:
# 1のnumpyバージョン
import numpy as np
def f():
    n = int(input())
    a = list(map(int, input().split()))
    x = list(sorted(set(a)))
    a = np.array(a, dtype="i8")
    Li = -1
    Ri = len(x) - 1
    while Li + 1 < Ri:
        i = (Li + Ri) // 2
        xi = x[i]
        s = 0
        lr = np.cumsum((a > xi) * 2 - 1, dtype="i8")
        M = np.sum((lr >= 0) * 2 - 1)
        for l in range(1, n):
            lr[l:] -= lr[l - 1]
            M += np.sum((lr[l:] >= 0) * 2 - 1)
        if M >= 0:
            Li = i
        else:
            Ri = i
    print(x[Ri])

f()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
a = np.array(a, dtype="i8")
Li = -1
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    s = 0
    lr = np.cumsum((a > xi) * 2 - 1, dtype="i8")
    M = np.sum((lr >= 0) * 2 - 1)
    for l in range(1, n):
        lr[l:] -= lr[l - 1]
        M += np.sum((lr[l:] >= 0) * 2 - 1)
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])

Submission status: Time Limit Exceeded

Solution code:
def update(i, x):
    while i < n:
        bit[i] += x
        i += i & -i


def getsum(i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


def f(n, a, x):
    Li = -1
    Ri = len(x) - 1
    i = (Li + Ri) // 2
    xi = x[i]
    for ai, ak in enumerate(a):
        update(ai + 1, (ak > xi) * 2 - 1)
    lr = [0] * n

    while 1:
        M = 0
        for r in range(n):
            lr[r] = tmp = getsum(r + 1)
            M += (tmp >= 0) * 2 - 1
        for l in range(1, n):
            for r in range(l, n):
                lr[r] = tmp = lr[r] - lr[l - 1]
                M += (tmp >= 0) * 2 - 1
        if M >= 0:
            Li = i
        else:
            Ri = i
        if Li + 1 == Ri: break
        pi = i
        i = (Li + Ri) // 2
        if i < pi:
            s = x[i + 1]
            b = x[pi]
            dt = 2
        else:
            s = x[pi + 1]
            b = x[i]
            dt = -2
        for ai, ak in enumerate(a):
            if s <= ak <= b:
                update(ai + 1, dt)
    print(x[Ri])


n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
bit = [0] * (n + 1)
f(n, a, x)

Submission status: Time Limit Exceeded

Solution code:
def update(i, x):
    while i < n:
        bit[i] += x
        i += i & -i


def getsum(i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


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

Li = -1
Ri = len(x) - 1
i = (Li + Ri) // 2
bit = [0] * (n + 1)
xi = x[i]
for ai, ak in enumerate(a):
    update(ai + 1, (ak > xi) * 2 - 1)
lr = [0] * n

while 1:
    M = 0
    for r in range(n):
        lr[r] = tmp = getsum(r + 1)
        M += (tmp >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] = tmp = lr[r] - lr[l - 1]
            M += (tmp >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
    if Li + 1 == Ri: break
    pi = i
    i = (Li + Ri) // 2
    if i < pi:
        s = x[i + 1]
        b = x[pi]
        dt = 2
    else:
        s = x[pi + 1]
        b = x[i]
        dt = -2
    for ai, ak in enumerate(a):
        if s <= ak <= b:
            update(ai + 1, dt)
print(x[Ri])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
Li = -1
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    lr = []
    s = 0
    M = 0
    for ak in a:
        s += (ak > xi) * 2 - 1
        lr += [s]
        M += (s >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] -= lr[l - 1]
            M += (lr[r] >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
Li = 0
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    a1 = [(ak > xi) * 2 - 1 for ak in a]
    lr = []
    s = 0
    M = 0
    for a1k in a1:
        s += a1k
        lr += [s]
        M += (s >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] -= lr[l - 1]
            M += (lr[r] >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input().strip())
A = list(map(int, input().strip().split(' ')))

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

print(median([median(A[i:j]) for i,j in itertools.combinations(list(range(N+1)),2)]))

Submission status: Time Limit Exceeded

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):
        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 >= math.ceil(comb/2) else binsearch(lft, half)

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