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:
# seishin.py
N = int(input())
*A, = map(int, input().split())

def solve(x):
    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
    c = 0; d = 10**18
    for a in A:
        if x <= a:
            c += 1
        else:
            c -= 1
        d = min(c, d)
    res = N*(N+1)//2
    c = -d+1
    for a in A:
        res -= get(c)
        if x <= a:
            c += 1
        else:
            c -= 1
        add(c, 1)
    return res <= N*(N+1)//4

left = min(A); right = max(A)+1
while left+1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
print(left)

Submission status: Time Limit Exceeded

Solution code:
'''
https://www.youtube.com/watch?v=5O4k1n5Ejzw
'''

n = int(input())
ptn = n * (n + 1) // 2
a = list(map(int, input().split()))

ans = min(a)
low, high = min(a), max(a)
csum = [0 for _ in range(n + 1)]

while low <= high:
    x = (low + high) // 2#最終的な答えとなる中央値の候補
    for i in range(n):
        csum[i + 1] = csum[i] + (1 if a[i] >= x else -1)#累積和, x以上を1, x未満を-1に置き換えた
    min_csum = min(csum)
    flgs = [0 for _ in range(max(csum) - min_csum + 1)]#[min, min + 1, ..., max - 1, max]
    cnts = 0
    for i in range(n + 1):#右端を選んでいる
        v = csum[i] - min_csum
        cnts += sum(flgs[:v + 1])#右以下の累積和となる左端の総数
        flgs[v] += 1
    if cnts * 2 >= ptn:
        ans = max(ans, x)
        low = x + 1
    else:
        high = x - 1
    #print(low, high, x)
    #print(b, csum, cnts, flgs)
    #print('ans', ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
https://www.youtube.com/watch?v=5O4k1n5Ejzw
'''

n = int(input())
ptn = n * (n + 1) // 2
a = list(map(int, input().split()))

ans = min(a)
low, high = min(a), max(a)
csum = [0 for _ in range(n + 1)]

while low <= high:
    x = (low + high) // 2#最終的な答えとなる中央値の候補
    for i in range(n):
        csum[i + 1] = csum[i] + (1 if a[i] >= x else -1)#累積和, x以上を1, x未満を-1に置き換えた
    min_csum = min(csum)
    flgs = [0 for _ in range(max(csum) - min_csum + 1)]#[min, min + 1, ..., max - 1, max]
    cnts = 0
    for i in range(n + 1):#右端を選んでいる
        v = csum[i] - min_csum
        cnts += sum(flgs[:v + 1])#右以下の累積和となる左端の総数
        flgs[v] += 1
    if cnts * 2 >= ptn:
        ans = max(ans, x)
        low = x + 1
    else:
        high = x - 1
    #print(low, high, x)
    #print(b, csum, cnts, flgs)
    #print('ans', ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
https://www.youtube.com/watch?v=5O4k1n5Ejzw
'''

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

ans = min(a)
low, high = min(a), max(a)
b = [0 for _ in range(n)]
csum = [0 for _ in range(n + 1)]

while low <= high:
    x = (low + high) // 2#最終的な答えとなる中央値の候補
    for i in range(n):
        b[i] = 1 if a[i] >= x else -1#x以上を1, x未満を-1に置き換えた
        csum[i + 1] = csum[i] + b[i]#累積和
    min_csum = min(csum)
    flgs = [0 for _ in range(max(csum) - min_csum + 1)]#[min, min + 1, ..., max - 1, max]
    cnts = 0
    for i in range(n + 1):#右端を選んでいる
        v = csum[i] - min_csum
        cnts += sum(flgs[:v + 1])#右以下の累積和となる左端の総数
        flgs[v] += 1
    if cnts * 2 >= (n * (n + 1) // 2):
        ans = max(ans, x)
        low = x + 1
    else:
        high = x - 1
    #print(low, high, x)
    #print(b, csum, cnts, flgs)
    #print('ans', ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
https://www.youtube.com/watch?v=5O4k1n5Ejzw
'''

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

ans = min(a)
low, high = min(a), max(a)
while low <= high:
    x = (low + high) // 2#最終的な答えとなる中央値の候補
    b = []
    for i in a:
        t = 1 if i >= x else -1
        b.append(t)#x以上を1, x未満を-1に置き換えた
    csum = [0]
    for i in b:
        csum.append(csum[-1] + i)#累積和
    flgs = [0 for _ in range(max(csum) - min(csum) + 1)]#[min, min + 1, ..., max - 1, max]
    cnts = 0
    for i in range(n + 1):#右端を選んでいる
        v = csum[i] - min(csum)
        cnts += sum(flgs[:v + 1])#右以下の累積和となる左端の総数
        flgs[v] += 1
    if cnts * 2 >= (n * (n + 1) // 2):
        ans = max(ans, x)
        low = x + 1
    else:
        high = x - 1
    #print(low, high, x)
    #print(b, csum, cnts, flgs)
    #print('ans', ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
# import time
# t0 = time.time()

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

dict_count = {}
seq_list = []

# t1 = time.time()
# print("#", t1 - t0)

a_sort = sorted(a) # Nlog(N)
left = 0
right = N - 1
while True: # log(N)
    i_m = left + (right - left + 1) // 2
    m = a_sort[i_m]
    a_comp = [2 * int(a[i] >= m) - 1 for i in range(N)] # N
    sum_a = 0
    # sum whether sum(a_comp[l, r] >= 0) for all (l, r)
    sum_temp = []
    for i, ai_comp in enumerate(a_comp): # N
        for j in range(i): # N
            sum_temp[j] += ai_comp
            sum_a += 2 * int(sum_temp[j] >= 0) - 1
        sum_temp.append(ai_comp)
        sum_a += ai_comp
    # update left of right
    if sum_a == 0: break
    elif sum_a < 0: right = i_m - 1
    else: left = i_m
    # escape
    if left == right: break

# ans
# t2 = time.time()
# print("#", t2 - t1)
print(m)

Submission status: Time Limit Exceeded

Solution code:
'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

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

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''

        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

'''
def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]
'''

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

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = [1 if a[i] >= X else -1 for i in range(N)]#1, -1に変換
    cum = [N]
    for i in range(N):
        cum.append(cum[i] + a_X[i]) #累積和を取るが、BITを使うため全部0以上に（初項N）
    b = BIT(2 * N + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)

Submission status: Time Limit Exceeded

Solution code:
'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

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

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''
        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

import numpy as np

def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]

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

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = np.array([1 if a[i] >= X else -1 for i in range(N)]) #1, -1に変換
    cum = np.hstack(([0], np.cumsum(a_X))) #累積和を取る
    min_cum = min(cum)
    cum -= min_cum - 1 #BITを使うために全部0以上に

    b = BIT(max(cum) + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)

Submission status: Time Limit Exceeded

Solution code:
'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

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

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''
        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

import numpy as np

def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]

N = int(input())
a = list(map(int, input().split()))
m = min(a)
M = max(a)

med_list= []
for i in range(N):
    for j in range(i + 1, N + 1):
        med_list.append(median(a[i:j]))

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = np.array([1 if a[i] >= X else -1 for i in range(N)]) #1, -1に変換
    cum = np.hstack(([0], np.cumsum(a_X))) #累積和を取る
    min_cum = min(cum)
    cum -= min_cum - 1 #BITを使うために全部0以上に

    b = BIT(max(cum) + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1
#区間[l, r)を2分探索
while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
# from statistics import median_high as med

def inversion(permList):
    if len(permList) == 1:
        return 0
    else:
        numInversion=len(permList)-permList.index(max(permList))-1
        permList.remove(max(permList))
        return numInversion+inversion(permList)

      
def convert(a, th):
  n = len(a)
  s_ = [None] * n
  tmp = 0
  for i in range(n):
    if a[i] >= th:
      tmp += n + 1
    else:
      tmp -= n
    s_[i] = tmp
  return s_
  
set_a = list(set(a))
set_a = sorted(set_a, reverse=True)

for th in set_a:
  s = convert(a, th)
  len_m = n * (n + 1) // 2
  inv = inversion(s)
  if not inv >= len_m // 2:
    break
  # print(th, convert(a, th), inv, inv >= len_m // 2)
print(th)
# print(inversion([1,0,0]))

Submission status: Time Limit Exceeded

Solution code:
#encoding utf 8
n = int(input())

a = list(int(i) for i in input().split())

def midle_pos(midle):
    return int(midle/2)

m = a
for i in range(1,n):
    for j in range(n-i):
        b = []
        b += a[j:j+i]
        b.sort()
        m.append(b[midle_pos(i)])

m.sort()
# print(m)
len = len(m)
print(m[midle_pos(len)])

Submission status: Time Limit Exceeded

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

def search(c):
    cnt = 0
    sign_list = [0] * N
    for i in range(N):
        sign_list[i] = 1 if a_list[i] >= c else -1
    
    cum_sign = [0] * (N+1)
    for i in range(N):
        cum_sign[i+1] = cum_sign[i] + sign_list[i]

    # O(N^2)だよねこれ。。    
    for l in range(N-1):
        for r in range(l+1,N):
            if cum_sign[r] - cum_sign[l] >= 0:
                cnt += 1
                
    #print(sign_list)
    #print(cum_sign)

    return cnt

# binary search
a_sorted = sorted(a_list)

left = 0
right = N
mid = N // 2
C = (N * (N-1)) // 2

while left < mid and mid < right:
    if search(a_sorted[mid]) > C // 2:
        left = mid
        mid = (mid + right) // 2
    else:
        right = mid
        mid = (mid + left) // 2
        
print(a_sorted[mid])

Submission status: Time Limit Exceeded

Solution code:
def findmedian(array):
	array = sorted(array)
	mid = len(array)//2
	return array[mid]

import bisect

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

sortmatrix = [[[] for i in range(a)] for j in range(a)]
median = []
	
for i in range(a):
	sortmatrix[i][i] = [m[i]]
	median.append(m[i])
	
for i in range(a):
	for j in range(i + 1, a):
		sortmatrix[i][j] = sortmatrix[i][j - 1]
		bisect.insort(sortmatrix[i][j-1], m[j])
		median.append(sortmatrix[i][j][len(sortmatrix[i][j])//2])
		
print (findmedian(median))

Submission status: Time Limit Exceeded

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

all_s = []
ans = {}
for a in A:
    for i in range(len(all_s)):
        all_s[i].append(a)
        all_s[i] = sorted(all_s[i])
        m = all_s[i][len(all_s[i]) // 2]
        ans[m] = ans.get(m, 0) + 1
    ans[a] = ans.get(a, 0) + 1
    all_s.append([a])

A = sorted(list(set(A)))
ans_N = int(0.5 * N * (N + 1)) // 2 + 1
tmp = 0
for a in A:
    tmp += ans[a]
    if(tmp >= ans_N):
        print(a)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

def getMed(X):
    X.sort()
    return X[len(X)/2]

N = sys.stdin.readline()
A = map(int, sys.stdin.readline().strip().split(" "))

l = []
for i in range(len(A)):
    for j in range(i,len(A)):
        l.append(getMed(A[i:j+1]))

print(getMed(l))

Submission status: Time Limit Exceeded

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

b = a[:]
for i in range(n):
	for j in range(1,n-i):
		c = a[i:i+j]
		c.sort()
		b.append(c[j//2])
b.sort()
print(b[(n*(n+1))//4])

Submission status: Time Limit Exceeded

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

L = []
for l in range(N):
    D = [0]
    for r in range(l, N):
        if r == l:
            bisect.insort_left(L, A[l])
            D[0] = A[l]
            continue
        bisect.insort_left(D, A[r])
        bisect.insort_left(L, D[len(D) // 2])

print(L[len(L)//2])

Submission status: Time Limit Exceeded

Solution code:
import statistics

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

l = []

if n > 10**3:
    a = a[n//2-5*(10**2):n//2+5*(10**2)]

for i in range(len(a)):
    for j in range(i,len(a)):
        l.append(statistics.median_high(a[i:j+1]))

print(statistics.median_high(l))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(int(i) for i in input().split())
l=[]
for i in range(n,0,-1):
    for j in range(0,i):
        b=a[j:i]
        b.sort()
        c=i-j
        if c%2==0:
            d=int(c/2)
            m=b[d]
        else:
            d=int((c-1)/2)
            m=b[d]
        l.append(m)
l.sort()
x=len(l)
if x%2==0:
    y=int(x/2)
    z=l[y]
else:
    y=int((x-1)/2)
    z=l[y]
print(z)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
m = []
for i in range(N):
    for j in range(i+1, N+1):
        b = a[i: j]

        #print(b)
        b.sort()
        lenth = len(b)
        manaka = lenth // 2
        #print(b[manaka])
        m.append(b[manaka])
nagasa = len(m)
mannaka = nagasa // 2
m.sort()
print(m[mannaka])

Submission status: Time Limit Exceeded

Solution code:
import statistics

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

l = []

if n > 10**4:
    a = a[n//2-5*(10**3):n//2+5*(10**3)]

for i in range(len(a)):
    for j in range(i,len(a)):
        l.append(statistics.median_high(a[i:j+1]))

print(statistics.median_high(l))

Submission status: Time Limit Exceeded

Solution code:
import statistics
N = int(input())
a = list(map(int, input().split()))

m = []
for i in range(N):
  for j in range(i+1,N+1):
    m.append(statistics.median_high(a[i:j]))
print(statistics.median_high(m))

Submission status: Time Limit Exceeded

Solution code:
import statistics

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

l = []



for i in range(len(a)):
    for j in range(i,len(a)):
        l.append(statistics.median_high(a[i:j+1]))

print(statistics.median_high(l))

Submission status: Time Limit Exceeded

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

def median(b,list):
	c = sorted(b)
	list.append(c[len(c)//2])
	return 0

m =[]

for t in range(n):
	for i in range(n-t):
		median(a[i:i+t+1],m)

x = []
median(m,x)
print(x[0])

Submission status: Time Limit Exceeded

Solution code:
import statistics
import math
import numpy as np

N = int(input())
an_list = list(map(int, input().split()))
med_list = np.arange(0)

for i in range(0,N+1):
    for j in range(i+1,N+1):
        if i != j :
            med_list = np.append(med_list, [statistics.median_high(np.array(an_list)[i:j])])
#             print(an_list[i:j])

print(statistics.median_high(med_list))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

for i in range(n):
    for j in range(i + 1, n + 1):
        m.append(sorted(a[i:j])[(j - i) // 2])

print(sorted(m)[len(m) // 2])

Submission status: Time Limit Exceeded

Solution code:
import statistics
n = int(input())
a = list(map(int,input().split()))
p = int(int(n *(n+1)/2)/2 + 1)
ans = a
flg = False
for i in range(2,n):
  for j in range(n-i):
    t = statistics.median_high(a[j:i+j])
    ans.append(t)
    if(ans.count(t) >= p):
      flg = True
      break
  if(flg):
    break
print(statistics.median_high(ans))

Submission status: Time Limit Exceeded

Solution code:
import statistics
import math
import numpy as np

N = int(input())
an_list = list(map(int, input().split()))
med_list = []

for i in range(0,N+1):
    for j in range(i+1,N+1):
            med_list.append(statistics.median_high(np.array(an_list)[i:j]))
#             print(an_list[i:j])

print(statistics.median_high(med_list))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=input().split()
a=list(int(i) for i in a)
l=[]
for i in range(n,0,-1):
    for j in range(0,i):
#        print(j,i)
        b=a[j:i]
#        print(b)
        b.sort()
        c=i-j
        if c%2==0:
            d=int(c/2)
            m=b[d]
        else:
            d=int((c-1)/2)
            m=b[d]
        l.append(m)
#print(l)
l.sort()
x=len(l)
if x%2==0:
    y=int(x/2)
    z=l[y]
else:
    y=int((x-1)/2)
    z=l[y]
print(z)

Submission status: Time Limit Exceeded

Solution code:
def median(alist):
	srtd = sorted(alist)
	mid = len(alist)//2
	return srtd[mid]

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

result = []

for i in range(1,a + 1):
	for j in range(a - i + 1):
		result.append(median(m[j:j+i]))
		
print (median(result))

Submission status: Time Limit Exceeded

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

def med(a):
    a.sort()
    if len(a) % 2 == 0:
        return(a[int(len(a)/2)])
    else:
        return(a[int((len(a)-1)/2)])

m = []

for i in range(1,N+1):
    for j in range(N-i+1):
        b = a[j:j+i]
        m.append(med(b))

ans = med(m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import statistics
import math
N = int(input())
an_list = list(map(int, input().split()))
med_list = []

for i in range(0,N+1):
    for j in range(i+1,N+1):
        if an_list[i:j] != []:
            med_list.append(statistics.median_high(an_list[i:j]))
#             print(an_list[i:j])

print(statistics.median_high(med_list))

Submission status: Time Limit Exceeded

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


def f(i, j):
    s = sorted(aa[i:j+1])
    return s[(j - i + 1) // 2]


x = sorted([f(i, j) for i in range(n) for j in range(i, n)])
print(x[len(x) // 2])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
from statistics import median_high as med

m = []

for l in range(n):
  for r in range(l, n):
    m.append(med(a[l:r+1]))
print(med(m))

Submission status: Time Limit Exceeded

Solution code:
import statistics
import math
N = int(input())
an_list = list(map(int, input().split()))
med_list = []

for i in range(0,N+1):
    for j in range(0,N+1):
        if an_list[i:j] != []:
            med_list.append(statistics.median_high(an_list[i:j]))
#             print(an_list[i:j])

print(statistics.median_high(med_list))

Submission status: Time Limit Exceeded

Solution code:
import statistics
n = int(input())
a = list(map(int,input().split()))
p = int(int(n *(n+1)/2)/2 + 1)
ans = []
flg = False
for i in range(1,n):
  for j in range(n-i):
    t = statistics.median_high(a[j:i+j])
    ans.append(t)
    if(ans.count(t) >= p):
      flg = True
      break
  if(flg):
    break
if(len(ans) == 0):
  ans = a
print(statistics.median_high(ans))

Submission status: Time Limit Exceeded

Solution code:
def median(l):
    return sorted(l)[len(l) // 2]

[N] = [int(i) for i in input().split()]

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

m = []
for i in range(N):
    for j in range(i + 1, N + 1):
        m.append(median(a[i:j]))


print(median(m))

Submission status: Time Limit Exceeded

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

peak=np.ceil(len(A)/2)+1
A.sort()
arr=[]
num=1
for Anum,i in enumerate(A):
    for k in range(num):
        arr.append(i)
    if Anum<peak:
        num+=1
    else:
        num-=1
#print(arr)

if len(arr)%2==0:
    print(arr[int(len(arr)/2)])
else:
    print(arr[int((len(arr)-1)/2)])

Submission status: Time Limit Exceeded

Solution code:
def med(arr):
    l = len(arr)
    arr.sort()
    return arr[l//2]

N = int(input())
arr = list(map(int, input().split(" ")))

right = 0
left = 0
meds = []
while left < N:
    right = 0
    while right < N:
        sub_arr = arr[left:right+1]
        if len(sub_arr) != 0:
            meds.append(med(sub_arr))
        right += 1
    left += 1

print(med(meds))

Submission status: Time Limit Exceeded

Solution code:
import statistics


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

B = []

for l in range(len(A)):
    for r in range(len(A)-l):
        B.append(statistics.median_high(A[l:l+1+r]))

print(statistics.median_high(B))

Submission status: Accepted

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):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def search(x):
    l = [1 if i >= x else -1 for i in a]
    c = [n]
    for i in range(n):
        c.append(c[-1]+l[i])

    count = 0
    bit = Bit(2*n+1)
    for i in c:
        count += bit.sum(i+1)
        bit.add(i,1)
    
    return x,count

k = (n*(n+1)/2+1)//2
le = 0
ri = max(a)+1

while ri > le + 1:
    m = (ri+le)//2
    ans,count = search(m)

    if count >= k:
        le = m
    else:
        ri = m
print(le)

Submission status: Accepted

Solution code:
# 座標圧縮した場合

import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()
C = sorted(list(set(A)))
dict_A = {}  # dict_A[a] = (a は A の中で何番目に小さい値か)
dict_C = {}  # dict_C[i] = (A の中で i 番目に小さい値)
for i in range(1,len(C)+1):
    dict_C[i] = C[i-1]
    dict_A[C[i-1]] = i
A = [dict_A[a] for a in A]


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  # 全て正になるように補正
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**5+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(dict_C[ok])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  # 全て正になるように補正
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N for b in B]
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b+1)
        bit.update(b+1,1)
    return True if count >= (N*(N+1)+3)//4 else False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
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 + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])