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:
N = int(input().strip())
nums = list(map(int, input().strip().split()))
nums_length = len(nums)
if nums_length == 1:
    print(nums[0])
else:
    median = []
    for i in range(nums_length):
        for j in range(i + 1, nums_length + 1):
            subarray = nums[i:j]
            subarray_length = len(subarray)
            if subarray_length == 1:
                key = subarray[0]
            else:
                ele = subarray[subarray_length - 1]
                for k in range(subarray_length - 2, -1, -1):
                    if subarray[k] > ele:
                        subarray[k + 1] = subarray[k]
                    else:
                        subarray[k + 1] = ele
                        break
                key = subarray[subarray_length//2]
            median.append(key)
            median_length = len(median)
            if median_length != 1:
                for k in range(median_length - 2, -1, -1):
                    if median[k] > key:
                        median[k + 1] = median[k]
                    else:
                        median[k + 1] = key
                        break

    print(median[len(median) // 2 + 1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
nums = list(map(int, input().strip().split()))
if len(nums) == 1:
    print(nums[0])
else:
    median = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums) + 1):
            if len(nums[i:j]) == 1:
                key = nums[i]
            else:
                subarray = sorted(nums[i:j])
                key = subarray[len(subarray)//2]
            median.append(key)
            if len(median) != 1:
                for k in range(len(median) - 2, -1, -1):
                    if median[k] > key:
                        median[k + 1] = median[k]
                    else:
                        median[k + 1] = key
                        break

    print(median[len(median) // 2 + 1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
#a=[5,4,6,7,2,8,4,6,2,6,1,30]
#print(a)
#left,rightはそれぞれソート済みの配列
#マージして転倒数を返す
def merge(left,right):
    L = len(left)
    R = len(right)
    indexL = 0
    indexR = 0
    mergedList = []
    answer = 0
    while indexL < L and indexR < R:
        lElem = left[indexL]
        rElem = right[indexR]
        if  lElem <= rElem:
            mergedList.append(lElem)
            indexL += 1
            #print(indexL,indexR,lElem)
        else:
            mergedList.append(rElem)
            answer += L - indexL
            indexR += 1
            #print(indexL,indexR,rElem)
    while indexL < L:
        mergedList.append(left[indexL])
        indexL += 1
    while indexR < R:
        mergedList.append(right[indexR])
        indexR += 1
    return(answer,mergedList)

def inversionNum(acc,xs):
    L = len(xs)
    if L <= 1:
        return((acc,xs))
    half = L//2
    left = xs[0:half]
    right = xs[half:]
    ansL,sortedL = inversionNum(0,left)
    ansR,sortedR = inversionNum(0,right)
    ansM, mergedList = merge(sortedL,sortedR)
    return((acc+ansL+ansR+ansM,mergedList))

def judge(x):
    """
    求める中央値がx以上であるときTrue, x未満であるときFalseを返す
    """
    accum=[0]
    index = 0
    L = len(a)
    while index < L:
        if a[index] >= x:
            accum.append(accum[index]+1)
        else:
            accum.append(accum[index]-1)
        index += 1
    invNum,sList = inversionNum(0,accum)

    return(invNum <= L*(L+1)//4)

def solve(ok,ng):
    """
    解が[ok,ng)に入ることを前提に2分探索をし、judge(x)==Trueとなる最大のxを求める。
    judge(x)の性質は2分探索が可能なものであることを仮定する。
    """
    if ok + 1 == ng:
        return(ok)
    mid = (ok+ng)//2
    if judge(mid):
        return(solve(mid,ng))
    else:
        return(solve(ok,mid))

print(solve(0,10**9+1))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
	# 0-index
	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):
		#print("check")
		while i <= self.size:
			#print(i)
			self.bit[i] += x
			i += (i & -i)

def search(n, mid_num, a_list):
	#print(n, mid_num, a_list)
	bit = BIT(2 * n + 2)
	result = 0
	tmp_sum = 0
	b_list = [1 if x >= mid_num else -1 for x in a_list]
	bit.add(n, 1)
	for i in range(n):
		tmp_sum += b_list[i]
		result += bit.sum(tmp_sum + n)
		bit.add(tmp_sum + n, 1)
		#print(tmp_sum, result, bit.bit)
	
	return result

def main():
	n = int(input())
	a_list = list(map(int, input().split()))

	a_list_sorted = sorted(a_list)
	ub = n
	lb = 0
	mid = n // 2
	th = (n * (n + 1) / 2 + 1) // 2

	while True:
		#print("lb, mid, ub", lb, mid, ub)
		if search(n, a_list_sorted[mid], a_list) >= th:
			if mid == n-1:
				break
			elif search(n, a_list_sorted[mid + 1], a_list) < th:
				break
			elif ub - lb <= 1:
				break
			else:
				lb = mid
				mid = (mid + ub) // 2
		else:
			ub = mid
			mid = (mid + lb) // 2

	print(a_list_sorted[mid])

def sub():
	search(3, 20, [10, 30, 20])
	print(" ")
	search(3, 30, [10, 30, 20])
	
if __name__ == '__main__':
	main()
	#sub()

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree:
	# 0-index
	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 sum_btw(i, j):
		return self.sum(j) - self.sum(i - 1)
 
	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += (i & -i)

def main():
	n = int(input())
	a_list = list(map(int, input().split()))

	a_list_sorted = sorted(a_list)
	ub = n
	lb = 0
	th = (n * (n + 1) / 2 + 1) // 2
	mid = (ub + lb) // 2
	mid_num = a_list_sorted[mid]

	while ub - lb > 1:		
		mid = (ub + lb) // 2
		mid_num = a_list_sorted[mid]

		bit = BinaryIndexedTree(2 * n + 2)
		result = 0
		tmp_sum = 0
		for i in range(n):
			if a_list[i] >= mid_num:
				tmp_sum += 1
			else:
				tmp_sum -= 1
			result += bit.sum(tmp_sum + n)
			bit.add(tmp_sum + n, 1)

		#print(mid, result)
		if result >= th:
			lb = mid
		else:
			ub = mid
	print(mid_num)
	

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import numpy

def main():
	n = int(input())
	a_list = list(map(int, input().split()))
	m = n * (n - 1) / 2

	candidate = sorted(a_list)
	left = 0
	right = n - 1
	mid = n // 2

	while True:		
		mid = (left + right) // 2
		#print(left, right, mid, candidate[mid], sub(candidate[mid], a_list), m)
		if sub(candidate[mid], a_list) >= m:
			if mid == n - 1:
				break
			elif sub(mid + 1, a_list) < m:
				break
			else:
				left = mid + 1
		else:
			right = mid + 1

		if mid == (left + right) // 2:
			break

	print(candidate[mid])

def trans_binary(x, a_list):
	return [-1 if a < x else 1 for a in a_list]

def count_num_sub(c_list_sub):
	if sum(c_list_sub) >= 0:
		return 1
	else:
		return 0

def count_num(c_list):
	ans = 0
	for i in range(len(c_list)):
		for j in range(i, len(c_list)):
			ans += count_num_sub(c_list[i:(j+1)])
	return ans

def sub(x, a_list):
	b_list = trans_binary(x, a_list)
	c_list = list(numpy.cumsum(b_list))
	ans = count_num(c_list)
	return ans

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from bisect import bisect_right

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


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(2 * N + 2)  # N+1番目が真ん中
target = (N * (N + 1) // 2 + 1) // 2

# にぶたん
l, r = -1, 10 ** 9 + 1

while r - l > 1:
    X = (r + l) // 2
    Binary = [0] + [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    temp = sorted(Binary)
    order = [bisect_right(temp, b) for b in Binary]
    inversion = 0

    for x in order:
        inversion += BIT.sum(x)
        BIT.add(x, 1)

    if inversion >= target:
        l = X
    else:
        r = X

print(r)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from bisect import bisect_right

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


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(2 * N + 2)  # N+1番目が真ん中
target = (N * (N + 1) // 2 + 1) // 2

# にぶたん
l, r = -1, 10 ** 9 + 1

while r - l > 1:
    X = (r + l) // 2
    Binary = [0] + [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    temp = sorted(Binary)
    order = [bisect_right(temp, b) for b in Binary]
    inversion = 0

    for x in order:
        inversion += BIT.sum(x)
        BIT.add(x, 1)

    if inversion >= target:
        l = X
    else:
        r = X

print(r)

Submission status: Time Limit Exceeded

Solution code:
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    ma=0
    mi=0
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
        ma=max(p[i],ma)
        mi=min(p[i],mi)
    tree=BIT(ma-mi+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]-mi+1)
        tree.add(p[i-1]-mi+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	#aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

	S = [0] #S_0 = 0を忘れずにつける
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	#S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
	#MIN = 0 , MAX = 6

	L = (MAX-MIN+1) #BITのサイズ L=6
	bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) #S_iの最小値が1となるように調整

		#BITで既出の要素のうちS_i以下の要素数をカウント
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		#BITのS_iに1を加算して更新
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans #中央値がx以上となる(l,r)の組の数

border = ( (N+1)*N//2 +1 )//2
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


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):
        self.tree = [0] * (self.size + 1)


def solve(n, aaa):
    t = n * (n + 1) // 4
    alt = sorted(set(aaa))
    l, r = 0, len(alt) - 1
    bt = Bit(n * 2)
    while l <= r:
        m = (l + r) // 2
        am = alt[m]
        ccc = accumulate(1 if a - am >= 0 else -1 for a in aaa)
        bt.add(n, 1)
        right_order = 0
        for p in ccc:
            p += n
            right_order += bt.sum(p)
            bt.add(p, 1)
        if right_order >= t:
            l = m + 1
        else:
            r = m - 1
        bt.reset()
    return alt[r]


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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):
        self.tree = [0] * (self.size + 1)


def solve(n, aaa):
    t = n * (n + 1) // 4
    alt = sorted(set(aaa))
    l, r = 0, len(alt) - 1
    bt = Bit(n * 2)
    while l <= r:
        m = (l + r) // 2
        ccc = ((((aaa - alt[m]) >= 0) * 2 - 1).cumsum() + n).tolist()
        bt.add(n, 1)
        right_order = 0
        for p in ccc:
            right_order += bt.sum(p)
            bt.add(p, 1)
        if right_order >= t:
            l = m + 1
        else:
            r = m - 1
        bt.reset()
    return alt[r]


n = int(input())
aaa = np.array(list(map(int, input().split())))
print(solve(n, aaa))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
_A = sorted(A)
def count_invension(A):
  _A = [[a, i] for i, a in enumerate(A)]
  _A.sort()
  BIT = [0] * len(_A)
  def get_sum(n):
    S = 0
    while n:
      S += BIT[n - 1]
      n -= n & (-n)
    return S
  def update(n, x):
    while n <= len(_A):
      BIT[n - 1] += x
      n += n & (-n)
  cnt = 0
  for i, (b, j) in enumerate(_A):
    cnt += i - get_sum(j + 1)
    update(j + 1, 1)
  return cnt
def binsearch(upper, lower):
  while upper - lower > 1:
    mid = (upper + lower) // 2
    B = [0] + [1 if a >= _A[mid] else -1 for a in A]
    for i in range(N):
      B[i + 1] += B[i]
    if count_invension(B) <= N * (N + 1) // 4:
      lower = mid
    else:
      upper = mid
  print(_A[lower])
binsearch(N, 0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
def count_invension(A):
  _A = [[a, i] for i, a in enumerate(A)]
  _A.sort()
  BIT = [0] * len(_A)
  def get_sum(n):
    S = 0
    while n:
      S += BIT[n - 1]
      n -= n & (-n)
    return S
  def update(n, x):
    while n <= len(_A):
      BIT[n - 1] += x
      n += n & (-n)
  cnt = 0
  for i, (b, j) in enumerate(_A):
    cnt += i - get_sum(j + 1)
    update(j + 1, 1)
  return cnt
def binsearch(upper, lower):
  while upper - lower > 1:
    mid = (upper + lower) // 2
    B = [0] + [1 if a >= mid else -1 for a in A]
    for i in range(N):
      B[i + 1] += B[i]
    if count_invension(B) <= N * (N + 1) // 4:
      lower = mid
    else:
      upper = mid
  print(lower)
binsearch(max(A) + 1, 0)

Submission status: Time Limit Exceeded

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

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

if N == 1:
    ans.append(A[0])
else:
    kuri = min(N+1, 30)
    for i in range(1, kuri):
        ans += Medi(A, i)


print(statistics.median_high(ans))

Submission status: Time Limit Exceeded

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

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

if N == 1:
    ans.append(A[0])
else:
    kuri = min(N+1, 50)
    for i in range(1, kuri):
        ans += Medi(A, i)


print(statistics.median_high(ans))

Submission status: Time Limit Exceeded

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

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

if N == 1:
    ans.append(A[0])
else:
    kuri = min(N+1, 100)
    for i in range(1, kuri):
        ans += Medi(A, i)


print(statistics.median_high(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N > 100000:
	print(sorted(A)[N//2])
	exit()

"""
val_idx_dict = {}
idx_val_dict = {}
A = sorted(A)
idx = 0
for a in A:
	if not a in val_idx_dict:
		val_idx_dict[a] = i
		idx_val_dict[i] = a
		i += 1
idx -= 1
"""

meds = []
for i in range(N):
	meds.append(A[i])
	befs = [None, A[i], None]
	for j in range(i+1, N):
		if j-i == 1:
			meds.append(max(A[i],A[j]))
			befs[1] = max(A[i], A[j])
			befs[0] = min(A[i], A[j])
		elif j-i == 2:
			befs = sorted([A[i],A[i+1],A[i+2]])
			meds.append(befs[1])
		else:
			if A[j] < befs[0] or A[j] > befs[2]:
				meds.append(befs[1])
			else:
				tmp = sorted(befs + [A[j]])
				if (j-i) % 2 == 1:
					befs = [tmp[0],tmp[1],tmp[2]]
					meds.append(befs[1])
				else:
					befs = [tmp[1],tmp[2],tmp[3]]
					meds.append(befs[1])
print(sorted(meds)[len(meds)//2])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ns = list(map(int,input().split()))
lis = []
for i in range(1,n+1):
    for j in range(n-i+1):
        l = ns[j:j+i]
        l.sort()
        m = len(l)
        lis.append(l[m//2])
lis.sort()
m = len(lis)
print(lis[m//2])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ns = list(map(int,input().split()))
lis = []
if n == 1:
  print(ns[0])
  quit()
if n == 2:
  print(max(ns))
  quit()
from random import randint
for _ in range(1000000):
    j = randint(1,n-2)
    i = randint(1,n-j)
    l = ns[j:j+i]
    l.sort()
    m = len(l)
    lis.append(l[m//2])
lis.sort()
m = len(lis)
print(lis[m//2])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

def dict_middle(d):
    items = sorted(d.items())
    length = sum(map(lambda x:x[1],items))
    tmp =0
    for key,val in items:
        tmp+=val
        if tmp>=length//2+1:
            return key

def guchoku():
    M = []
    for i in range(N):
        for j in range(i+1,N+1):
            M.append(get_middle(A[i:j]))
    return get_middle(M)

INF = float('inf')
d = defaultdict(int)

def shutsugen(i):
    i = min(i,N-i-1)+1
    ans = 0
    for length in range(1,N//2+2):
        ans += min(i,length) * (2 if (length != N//2+1 or N%2==0) else 1)
        #print("I:",ans,length)
    return ans

    # ans = 0
    # left = i-1
    # right = N-i
    # #left < right
    # for x in range(1,N+1):
    #     #x= min(x,N-x-1)
    #     if x<left:
    #         ans +=x
    #     elif left < x:
    #         ans +=
    #
    #         ans+= i
    #     elif i+x >= N:
    #         ans += N-x+1
    #     else:
    #         ans +=1
    #     print(i,x,ans,"hoge")
    # return ans





for i in range(1,N+1):
    if i%2==0:
        d[INF] +=  N-i+1
for i in range(N):
    val = A[i]
    #count = N+ min(i,N-i-1)
    d[val] +=shutsugen(i)

#print(sorted(d.items()))
print(dict_middle(d))
#print(guchoku())

Submission status: Time Limit Exceeded

Solution code:
import random
def f(A):
    L=[]
    N=len(A)
    for l in range(N+1):
        for r in range(l+1,N+1):
            B=sorted(A[l:r])
            K=len(A[l:r])
            L.append(B[K//2])
            #print(B[K//2],B)
    M=len(L)
    L.sort()
    #print(M,L)
    return L[M//2]
def g(A):
    N=len(A)
    return A[(N-1)//2]
N=int(input())
a=[int(i) for i in input().split()]
print(f(a))

Submission status: Time Limit Exceeded

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

def getMed(l, r):
    return sorted(a[l:r + 1])[(r - l + 1)//2]

result = []
for l in range(n):
    for r in range(l,n):
        result.append( getMed(l, r))
print(sorted(result)[len(result)//2])

Submission status: Time Limit Exceeded

Solution code:
N = int( input())
A = list( map( int, input().split()))
B = []
for k in range(1, N+1):
    L = k//2
    for i in range(0, N-k+1):
        C = A[i:i+k]
        C.sort()
        B.append(C[L])
B.sort()
print( B[ ((N+1)*N)//4])

Submission status: Time Limit Exceeded

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

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

ans = []

if N == 1:
    ans.append(A[0])
else:
    for i in range(1, N):
        ans += Medi(A, i)

print(statistics.median_high(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

def getMedian(a, l, r):
    M = (r-l)//2
    b = sorted(a[l:r])
    return b[M]


def main():
    n = int(sys.stdin.readline().rstrip())
    a = [int(v) for v in sys.stdin.readline().rstrip().split(' ')]

    #d = {v: 0 for v in set(a)}
    d = []

    c = 0
    for l in range(1, n+1):
        for i in range(0, n-l+1):
            #v = getMedian(a, i, i+l)
            #d[v] += 1
            #c += 1
            d.append(getMedian(a, i, i+l))

    #M = c//2 + 1
    print(getMedian(d, 0, len(d)))

    #z = 0
    #for i in sorted(d.items()):
    #    z += i[1]
    #    if z>=M:
    #        print(i[0])
    #        break

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import statistics
# S = input()
N = int(input())
A = list(map(int, input().split()))
# LR = [list(map(int, input().split())) for _ in range(M)]

def Medi(Arra , Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        tmp = []
        for j in range(Haba):
            tmp.append(A[i_M + j])
        re.append(statistics.median_high(tmp))
    return re

ans = []

if N == 1:
    ans.append(A[0])
else:
    for i in range(1, N):
        ans += Medi(A, i)

print(statistics.median_high(ans))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc101/tasks/arc101_b
"""
タグ: 中央値、二分探索、転倒数
"""
class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

def test(x):
    S = [0]
    for a in A:
        if a >= AS[x]:
            S.append(S[-1]+1)
        else:
            S.append(S[-1]-1)
    B = BitSet2(S,S)
    cnt = M - B.flip_counter()
    return cnt >= ceil(M/2)

import sys
from math import ceil
input = sys.stdin.readline

N = int(input())
M = N*(N+1)//2
A = list(map(int, input().split()))
AS = sorted(A)
print(AS[binary_search_int(0,N,test)])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc101/tasks/arc101_b
"""
タグ: 中央値、二分探索、転倒数
"""
class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

def test(x):
    S = [0]
    for a in A:
        if a >= x:
            S.append(S[-1]+1)
        else:
            S.append(S[-1]-1)
    B = BitSet2(S,S)
    cnt = M - B.flip_counter()
    return cnt >= ceil(M/2)

import sys
from math import ceil
input = sys.stdin.readline

N = int(input())
M = N*(N+1)//2
A = list(map(int, input().split()))
AS = sorted(A)
mi, ma = AS[0], AS[-1]
print(binary_search_int(mi,ma+1,test))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 

def check(k):
    li=[]
    for i in range(N):
        li.append(1 if A[i]<=k else 0)

    c=[0]*(N+1)
    for i in range(N):
        c[i+1]=c[i]+li[i]
        
    d=[]
    for i in range(N+1):
        d.append(2*c[i]-i)
        
    S=sorted(set(d))
    dic={}
    for i,x in enumerate(S):
        dic[x]=i
    
    bit=BIT(N+1)
    res=0
    for i in range(N+1):
        bit.add(dic[d[i]],1)
        res+=bit.get(dic[d[i]])
    
    if res>M:
        return True
    else:
        return False

N=int(input())
A=list(map(int,input().split()))
M=N*(N+1)//4
l,r=-1,max(A)+1
while(r-l>1):
    k=(l+r)//2
    if check(k):
        r=k
    else:
        l=k

print(r)

Submission status: Accepted

Solution code:
n=int(input())
*a,=map(int, input().split())
def invr(x):
    if len(x)<=1:
        return x,0
    m=len(x)
    x1=x[:m//2]
    x2=x[m//2:]
    x11,res1=invr(x1)
    x22,res2=invr(x2)
    rx=[];res=res1+res2
    l=0;r=0
    while l<m//2 and r<m-(m//2):
        if x11[l]<=x22[r]:
            rx.append(x11[l])
            l+=1
        else:
            rx.append(x22[r])
            r+=1
            res+=m//2-l
    rx+=x11[l:]
    rx+=x22[r:]
    return rx,res

def f(m):
    a2=[(ai>=m)*2-1 for ai in a]
    a3=[0]
    for ai in a2:
        a3.append(a3[-1]+ai)
    _,r=invr(a3)
    return n*(n+1)//2-r>=((n+1)*n//2)//2



mx=max(a)+1;mn=min(a)
while mx-mn>1:
    md=(mx+mn)//2
    r=f(md)
    if r:
        mn=md
    else:
        mx=md
print(mn)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n = int(input())
a = list(map(int, input().split()))
from collections import Counter
def sub(x):
    l = [1 if item>=x else -1 for item in a]
    count = [0] * (2*n+2)
    count[n] = 1
    i = n
    cumsum = 1
    ans = 0
    for item in l:
        i += item
        if item==1:
            cumsum += count[i]
        else:
            cumsum -= count[i+1]
        ans += cumsum
        count[i] += 1
        cumsum += 1
    return ans

l = 0
r = 10**9+1
tmp = (n+1)*n//2
thre = tmp//2 + tmp%2
while l<r-1:
    m = (l+r)//2
    if sub(m)>=thre:
        l = m
    else:
        r = m
print(l)