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: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline


def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l
    
    def reset(self):
        self.bit = [0]*(self.n+1)
        self.value = [0]*(self.n+1)


def main():
    n = int(input())
    b = list(map(int, input().split()))
    a = [[int(i), int(x)] for i, x in enumerate(b)]

    compress(a)
    key_list = dict()
    for i, x in a:
        key_list[x] = b[i-1]
    a = [x[1] for x in a]
    
    l, r = 0, max(a)
    bit = BIT(n+3)
    border = ((n+1) * n // 2 - 1) // 2 + 1

    while r-l > 1:
        k = (l+r) // 2

        s = [0]*(n+1)
        for i in range(n):
            if a[i] >= k:
                s[i+1] += 1
            else:
                s[i+1] -= 1
            s[i+1] += s[i]
        floor = min(s)
        for i in range(n+1):
            s[i] -= floor-1

        count = 0
        bit.reset()
        for i in range(n+1):
            count += bit.sum(s[i])
            bit.add(s[i]+1, 1)
        
        if count >= border:
            l = k
        else:
            r = k
    
    print(key_list[r])

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline


def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [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):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l
    
    def reset(self):
        self.bit = [0]*(self.n+1)
        self.value = [0]*(self.n+1)


def main():
    n = int(input())
    b = list(map(int, input().split()))
    a = [[int(i), int(x)] for i, x in enumerate(b)]

    compress(a)
    key_list = dict()
    for i, x in a:
        key_list[x] = b[i-1]
    a = [x[1] for x in a]
    
    l, r = 0, max(a)
    bit = BIT(n+3)
    border = (n+1) * n // 4 + 1

    while r-l > 1:
        k = (l+r) // 2

        s = [0]*(n+1)
        for i in range(n):
            if a[i] >= k:
                s[i+1] += 1
            else:
                s[i+1] -= 1
            s[i+1] += s[i]
        floor = min(s)
        for i in range(n+1):
            s[i] -= floor-1

        count = 0
        bit.reset()
        for i in range(n+1):
            count += bit.sum(s[i])
            bit.add(s[i]+1, 1)
        
        if count >= border:
            l = k
        else:
            r = k
    
    print(key_list[r])

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = N*(N+1)//2 - 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: Wrong Answer

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[1:],S[1:])
    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: Wrong Answer

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

print(sorted(a))
a = sorted(a)
def med(x):   
    return sorted(x)[len(x)//2]

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

print(med(m))

Submission status: Wrong Answer

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[1:])##?
    return n*(n+1)//2-r>=((n+1)*n//2)//2+1



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: Wrong Answer

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+1



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: Wrong Answer

Solution code:
n=int(input())
*a_,=map(int, input().split())
import numpy as np
a=np.array(a_)
def invr(x):
    if len(x)<=1:
        return x,0
    m=len(x)
    x1=x[:m//2]
    x2=x[m//2:]
    x11,r1=invr(x1)
    x22,r2=invr(x2)
    x11=x11[::-1]
    x22=x22[::-1]
    rx=[];r=r1+r2
    while x11 and x22:
        if x11[-1]<=x22[-1]:
            rx.append(x11.pop())
        else:
            rx.append(x22.pop())
            r+=len(x11)
    rx+=x11[::-1]
    rx+=x22[::-1]
    return rx,r

def f(m):
    a2=(a>=m)*2-1
    ac=np.cumsum(a2).tolist()
    _,r=invr([0]+ac)
    return n*(n+1)//2-r>=((n+1)*n//2)//2+1



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: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = (n * (n + 1) // 2) // 2 + 1


def check(x):
    # MofM が x以下である
    # x以下の要素が (n*(n+1)//2)//2 + 1 個以上ある
    cnt = 0
    for i in range(n):
        if a[i] <= x:
            cnt += 1
            cnt += min(i, n - 1 - i)
            cnt += min(i, n - i)
    return cnt >= m


lb = 0  # False
ub = max(a)  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Wrong Answer

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


def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)

#A1 ~ Aiまでの和 O(logN)
def query(bit,i):
    res_sum = 0
    while i > 0:
        res_sum += bit[i]
        i -= i&(-i)
    return res_sum

#Ai += x O(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


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

    ### BIT 
    #A1 ... AnのBIT(1-indexed)
    bit = [0]*(2*n+1)
    update(bit, n+1, 1)
    ans = 0
    total = 1
    for v in cumsum:
        ans += query(bit, v+n)
        update(bit, n+v+1, 1)
        total += 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)

Submission status: Wrong Answer

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

def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)

#A1 ~ Aiまでの和 O(logN)
def query(bit,i):
    res_sum = 0
    while i > 0:
        res_sum += bit[i]
        i -= i&(-i)
    return res_sum

#Ai += x O(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


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

    ### BIT 
    #A1 ... AnのBIT(1-indexed)
    bit = [0]*(2*n+1)
    update(bit, n+1, 1)
    ans = 0
    total = 1
    for v in cumsum:
        ans += (total - query(bit, -v+n))
        update(bit, n+v+1, 1)
        total += 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)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
N = int(input() )
M = input().split() 
M=[int(a) for a in M]
M=np.array(M)
medians=[]
if N<10**5 and max(M)<10**9:
    for v in itertools.combinations_with_replacement(range(N), 2):
            m=M[v[0]:v[1]+1]
            m=np.sort(m)
            mid=int(len(m)/2)
            medians.append(m[mid])
    medians=np.sort(np.array(medians))
    mid2=int(len(medians)/2)
    print(medians[mid2])

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input() )
M = input().split() 
M=[int(a) for a in M]
M=np.array(M)
medians=[]
M=np.sort(M)
for i in range(len(M)):
    for j in range(i,len(M),1):
        m=M[i:j+1]
        mid=int(len(m)/2)
        medians.append(m[mid])
mid2=int(len(medians)/2)
print(medians[mid2])

Submission status: Wrong Answer

Solution code:
print("yuki")

Submission status: Wrong Answer

Solution code:
# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
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
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if max_i - min_i <= 1:
            return min_i
        if func(index) <= target:
            index, min_i = (index + max_i)//2, index
            continue
        index, max_i = (index-1 + min_i)//2, index-1

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))

Submission status: Wrong Answer

Solution code:
# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
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
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if max_i - min_i <= 1:
            return index
        if func(index) <= target:
            index, min_i = (index + max_i)//2, index
            continue
        index, max_i = (index-1 + min_i)//2, index-1

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))

Submission status: Wrong Answer

Solution code:
# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
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
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        print(p)
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(c) for c in input().split()]
print(A[N//2]);

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]


class BinaryIndexedTree:
    """
        Parameters
        ----------
        array : list
            to construct BIT from
        f : func
            binary operation of the abelian group
        fi : func
            inverse mapping of f
            i.e. f(a, b) == c <-> fi(c, a) == b
        e : 
            identity element of the abelian group
        size : int
            limit for array size
    """

    def __init__(self, array, f, fi, e, size):
        self.f = f
        self.fi = fi
        self.e = e
        self.size = size
        self.n = len(array)
        self.dat = [e] * (size + 1)
        self.array = [e] * size
        self.build(array)

    def build(self, array_):
        for i, v in enumerate(array_):
            self.modify(i, v)

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        dv = fi(v, array[p])
        array[p] = v
        p += 1
        while p <= size:
            dat[p] = f(dat[p], dv)
            p += p & -p

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        return self.fi(self._query(r), self._query(l))

    def _query(self, p):
        dat, f, res = self.dat, self.f, self.e
        while p:
            res = f(res, dat[p])
            p -= p & -p
        return res


e = 0
size = 2 * N + 2
f = lambda a, b: a + b
fi = lambda c, a: c - a
offset = N


def check(x):
    cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
    # sum([l:r)) = cumsum[r] - cumsum[l] >= 0
    # ⇔ cumsum[l] <= cumsum[r]
    BIT = BinaryIndexedTree([e] * size, f=f, fi=fi, e=e, size=size)
    count = 0
    for c in cumsum:
        c += offset
        count += BIT.query(0, c + 1)
        BIT.modify(c + 1, BIT.query(c + 1, c + 2) + 1)
    return 2 * count > N * (N + 1) // 2


A_sorted = [0] + sorted(set(A)) + [10**10]
lb = 0
rb = len(A_sorted) - 1
# check(x) == Trueとなる最小のx
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(A_sorted[mid]):
        rb = mid
    else:
        lb = mid
print(rb)

Submission status: Wrong Answer

Solution code:
# PythonではTLE, PyPyだとAC
n = int(input())
a = list(map(int, input().split()))

class BIT:
    def __init__(self, n):
        self.n = 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.n:
            self.bit[i] += x
            i += i&(-i)
            
a_sorted = sorted(list(set(a)))
left, right = 0, len(a_sorted) # number of unique elements of a
while right-left > 1: # bisection search: O(logA)
    mid = (left+right)//2 # target index
    num = 0 # number of ranges with majority >= a_sorted[mid]
    bit = BIT(2*n+1) # initialize BIT: #regsum = bit.sum(regsum(+n))
    sum_ = 0 # region sum
    bit.add(sum_+n, 1)
    for i in range(n): # O(n)
        sum_ += 1 if a[i] >= a_sorted[mid] else -1 # update region sum by comaprison
        num += bit.sum(sum_+n) # add #ranges by sum_+n: O(logn)
        bit.add(sum_+n, 1) # increment BIT element at sum_+n(=count of interested regions)
    # print(bit.bit, left, right)

    # update search range
    if num > n*(n+1)//4:
        left = mid
    else:
        right = mid
print(a_sorted[left])

Submission status: Wrong Answer

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

class BIT:
    def __init__(self, n):
        self.n = 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.n:
            self.bit[i] += x
            i += i&(-i)
            
left, right = 0, 10**9
geta = n+1
while right-left > 1:
    mid = (left+right)//2
    num = 0
    bit = BIT(2*n+1)
    sum_ = 0
    bit.add(sum_+geta, 1)
    for i in range(n):
        val = 1 if a[i] <= mid else -1
        sum_ += val
        num += bit.sum(sum_+geta-1) - bit.sum(0)
        bit.add(sum_+geta, 1)

    print(bit.bit)
    if num > n*(n+1)//4:
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
import math

INF = float("inf")


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

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

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

    def reset(self):
        for i in range(self.size):
            self.tree[i] = 0


def solve(N: int, a: "List[int]"):

    cand = sorted(a)
    # 2分探索
    left = 0
    right = N
    C = math.ceil((N+1)*N/2/2)
    b = Bit(N*2+1)
    while left + 1 != right:    # [left, right) O(logN)
        xi = (left + right)//2
        x = cand[xi]
        # s, u = 0, 0
        # t = [0]*(2*N+1)
        # for i, av in enumerate(a):
        #     if x <= av:
        #         s += 1          # 今の数(総和)
        #         t[N+s] += 1       # s以下の合った個数
        #         u += t[N+s]          # 順序の正しい数
        #     else:
        #         s -= 1
        #         t[N+s] += 1
        #         u += t[N+s]
        # print(u)
        # print(t)

        t = [2*(x <= av)-1 for av in a]  # O(N)
        S = list(accumulate(t))         # O(N)
        u = 0
        b.reset()               # O(2N+1)
        for i, v in enumerate(S):  # O(2N+1)
            b.add(N+v, 1)         # O(log(2N+1))
            u += b.sum(N+v)
        # print("x", x, "(left, right)=({},{})".format(left, right))
        # print("u", u)
        # print(S)
        if u >= C:
            left = xi
        else:
            right = xi
    print(cand[left])
    return


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]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
alist=list(map(int,input().split()))
numdict={}
if len(alist)==1:
  print(alist[0])
  exit()

for x in alist:
  if x in numdict:
    numdict[x]+=1
  else:
    numdict[x]=1

medilist=alist.copy()

for i in range(1,N):
  newmedilist=[]
  if i%2:
    for x in range(0,N-i):
      num=max(medilist[x],alist[x+i])
      numdict[num]+=1
      newmedilist.append(num)
  else:
    for x in range(0,N-i):
      num=min(medilist[x],alist[x+i])
      numdict[num]+=1
      newmedilist.append(num)
  medilist=newmedilist

b=N*(N+1)//4+1

numlist=sorted(numdict.keys())

c=0
for x in numlist:
  c+=numdict[x]
  if c>=b:
    break

print(x)

Submission status: Wrong Answer

Solution code:
N=int(input())
alist=list(map(int,input().split()))
numdict={}
if len(alist)==1:
  print(alist[0])
  exit()

for x in alist:
  if x in numdict:
    numdict[x]+=1
  else:
    numdict[x]=1

medilist=alist.copy()

for i in range(1,N):
  newmedilist=[]
  print (medilist)
  if i%2:
    for x in range(0,N-i):
      num=max(medilist[x],alist[x+i])
      numdict[num]+=1
      newmedilist.append(num)
  else:
    for x in range(0,N-i):
      num=min(medilist[x],alist[x+i])
      numdict[num]+=1
      newmedilist.append(num)
  medilist=newmedilist

b=N*(N+1)//4+1

numlist=sorted(numdict.keys())

c=0
for x in numlist:
  c+=numdict[x]
  if c>=b:
    break

print(x)

Submission status: Wrong Answer

Solution code:
N=int(input())
alist=list(map(int,input().split()))
numdict=[]
amount=0
if len(alist)==1:
  print(alist[0])
  exit()
i=1
for x in range(0,((N+1)//2)):
  numdict.append([alist[x],i])
  amount+=i
  i+=2
i=2
for x in range(N-1,((N+1)//2)-1,-1):
  numdict.append([alist[x],i])
  amount+=i
  i+=2

numdict.sort()

b=(amount//2)+1
c=0

for x in range(0,N):
  c+=numdict[x][1]
  if c>b:
    break



print(numdict[x][0])

Submission status: Wrong Answer

Solution code:
N=int(input())
alist=list(map(int,input().split()))
numdict=[]
amount=0
if len(alist)==1:
  print(alist[0])
  exit()
i=1
for x in range(0,((N+1)//2)):
  numdict.append([alist[x],i])
  amount+=i
  i+=2
i=2
for x in range(N-1,((N+1)//2)-1,-1):
  numdict.append([alist[x],i])
  amount+=i
  i+=2

numdict.sort()

b=(amount//2)+1
c=0

for x in range(0,N):
  c+=numdict[x][1]
  if c>=b:
    break



print(numdict[x][0])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
MED = []
for i in range(N):
    j = 0
    for j in range(N-i):
        karilist = a[i:j+i+1]
        karilist.sort()
        karilen = len(karilist)
        med = karilist[int(karilen/2)]
        MED.append(med)
mlen = len(MED)
print(MED[int(mlen/2)])