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:
def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

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

        # 位置iに値vを足す
        def add(self, i, v):
            x = i+1
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    if n == 1:
        print(a[0])
        return
    ok = 0
    ng = 10**9+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        b = [0]+list(ac([(i >= mid)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def f(A):
  A.sort()
  return A[len(A)//2]
ml=[]
for l in range(N):
  for r in range(l,N):
    ml.append(f(A[l:r+1]))
print(f(ml))

Submission status: Time Limit Exceeded

Solution code:
#!python3

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


class SegmentTree:

    def __init__(self):
        self.n = self.array_n()
        self.dat = [0] * (self.n * 2 - 1)
        self.l = [None] * (self.n * 2 - 1)
        self.r = [None] * (self.n * 2 - 1)
        self.set_range(0, 0, self.n)

    @staticmethod
    def array_n():
        n = 1
        while n < 2 * N + 1:
            n *= 2
        return n

    def clear(self):
        self.dat = [0] * (self.n * 2 - 1)
    
    def set_range(self, num, left, right):
        self.l[num] = left
        self.r[num] = right
        if num < self.n - 1:
            self.set_range(2 * num + 1, left, (left + right) // 2)
            self.set_range(2 * num + 2, ((left + right) // 2), right)

    def index(self, x):
        return (self.n - 1) + x + N

    def add(self, x):
        i = self.index(x)
        while i > 0:
            self.dat[i] += 1
            i = (i - 1) // 2
        self.dat[0] += 1
    
    def sum_recur(self, num, right):
        if self.r[num] == right:
            return self.dat[num]
        h = (self.l[num] + self.r[num]) // 2
        if right <= h:
            return self.sum_recur(num * 2 + 1, right)
        else:
            return self.dat[num * 2 + 1] + self.sum_recur(num * 2 + 2, right)

    def sum(self, x):
        right = N + x + 1
        return self.sum_recur(0, right)
    
    
def judge(bit, n, x):
    v = 0
    s = 0
    for e in a:
        bit.add(s)
        if e < x:
            s -= 1
        else:
            s += 1
        v += bit.sum(s)
    
    if v < n:
        return False
    else:
        return True


def main():
    n = (N ** 2 + N) // 2
    if n % 2 == 0:
        n //= 2
    else:
        n = n // 2 + 1

    # binary search
    bit = SegmentTree()
    left, right = 1, 10 ** 9 + 1
    while right - left > 1:
        x = (left + right) // 2
        bit.clear()
        if judge(bit, n, x):
            left = x
        else:
            right = x
    
    print(left)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import numpy as np


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


def judge(n, x):
    l = np.cumsum(np.where(a < x, -1, 1))
    l = np.append(0, l)
    v = 0
    for i in range(1, N + 1):
        v += np.count_nonzero(l[:i] <= l[i])
    if v < n:
        return False
    else:
        return True


def main():
    n = (N ** 2 + N) // 2
    if n % 2 == 0:
        n //= 2
    else:
        n = n // 2 + 1
    
    # binary search
    left, right = 1, a.max() + 1
    while right - left > 1:
        x = (left + right) // 2
        if judge(n, x):
            left = x
        else:
            right = x
    
    print(left)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def add(i,x):
        while i<=size:
            tree[i]+=x
            i+=i&-i
    n,*a=map(int,open(0).read().split())
    size=n-~n
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        tree=[0]*-~size
        c=n+1
        s=0
        add(c,1)
        for t in a:
            c+=1if t>=mid else-1
            i=c
            while i:
                s+=tree[i]
                i-=i&-i
            add(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def sum(i):
        s=0
        while i:
            s+=tree[i]
            i-=i&-i
        return s
    def add(i,x):
        while i<=size:
            tree[i]+=x
            i+=i&-i
    n,*a=map(int,open(0).read().split())
    size=n-~n
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        tree=[0]*-~size
        c=n+1
        s=0
        add(c,1)
        for t in a:
            c+=1if t>=mid else-1
            s+=sum(c)
            add(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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 main():
    n,*a=map(int,open(0).read().split())
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        b=BIT(n-~n)
        badd,bsum=b.add,b.sum
        c=n+1
        s=0
        badd(c,1)
        for t in a:
            c+=1if t>=mid else-1
            s+=bsum(c)
            badd(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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
n,*a=map(int,open(0).read().split())
m=n*-~n//2+1>>1
ng=max(a)+1
ok=0
while ng-ok>1:
    mid=(ok+ng)//2
    b=BIT(n-~n)
    c=n+1
    s=0
    b.add(c,1)
    for t in a:
        c+=1if t>=mid else-1
        s+=b.sum(c)
        b.add(c,1)
    if s>=m:ok=mid
    else:ng=mid
print(ok)

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


n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int)
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = np.sort(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = np.where(A >= x, 1, -1)
    cumsum = np.hstack([np.array([n]), np.cumsum(up_or_down) + n])

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

Submission status: Time Limit Exceeded

Solution code:
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


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = [n]
    total = n
    for point in up_or_down:
        total += point
        cumsum.append(total)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

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


n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int64)
all_pattern = n * (n+1) // 2
check = all_pattern // 2
X = np.sort(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = np.where(A >= x, 1, -1)
    cumsum = np.cumsum(up_or_down) + n

    tree = Bit(2*n+1)
    pattern = 0
    for i, p in enumerate(cumsum, 1):
        tree.add(p, 1)
        pattern += tree.sum(p)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2
def ok(x):
    S = list(accumulate(1 if a >= x else -1 for a in A))
    ms = min(min(S), 0)
    S = [1] + [s - ms + 1 for s in S]
    L = max(S) + 1
    B = [0] * L
    c = 0
    for s in S:
        i = s
        while i > 0:
            c += B[i]
            i -= i & -i
        i = s
        while i < L:
            B[i] += 1
            i += i & -i
    return c >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


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


def test(A):
    N = len(A)
    M = []
    for l in range(N):
        for r in range(l + 1, N + 1):
            M.append(median(A[l:r]))
    print(median(M))


def less_than(k):
    arr = [0] * (N + 1)
    for i, b in enumerate(B):
        arr[i + 1] = 1 if b >= k else -1
    cum = cumsum(arr)
    base = min(cum)
    for i in range(len(cum)):
        cum[i] -= base

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=max(cum) + 1)
    count = 0
    for i, c in enumerate(cum):
        count += i - bit.sum(c + 1)
        bit.add(c, 1)

        # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
        # NH2 = (N+1)C2
        if count > (N + 1) * N // 2 / 2:
            return True
    return False


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
# test(A)

indices = argsort(A)

# 座圧
B = compress(A)

lo = 0
hi = N
while abs(lo - hi) > 1:
    mid = (lo + hi) // 2
    if less_than(B[indices[mid]]):
        hi = mid
    else:
        lo = mid
print(A[indices[lo]])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


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


def test(A):
    N = len(A)
    M = []
    for l in range(N):
        for r in range(l + 1, N + 1):
            M.append(median(A[l:r]))
    print(median(M))


def less_than(k):
    arr = [0] * (N + 1)
    for i, b in enumerate(B):
        arr[i + 1] = 1 if b >= k else -1
    cum = cumsum(arr)
    idx = argsort(cum)

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=len(cum) + 1)
    count = 0
    while idx:
        n = cum[idx[-1]]
        li = []
        while idx and cum[idx[-1]] == n:
            li.append(idx.pop())
        for i in li:
            count += bit.sum(i)
        for i in li:
            bit.add(i, 1)

        # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
        # NH2 = (N+1)C2
        if count > (N + 1) * N // 2 / 2:
            return True
    return False


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
# test(A)

indices = argsort(A)

# 座圧
B = compress(A)

lo = 0
hi = N
while abs(lo - hi) > 1:
    mid = (lo + hi) // 2
    if less_than(B[indices[mid]]):
        hi = mid
    else:
        lo = mid
print(A[indices[lo]])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


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


def test(A):
    N = len(A)
    M = []
    for l in range(N):
        for r in range(l + 1, N + 1):
            M.append(median(A[l:r]))
    print(median(M))


def less_than(k):
    arr = [0] * (N + 1)
    for i, b in enumerate(B):
        arr[i + 1] = 1 if b >= k else -1
    cum = cumsum(arr)
    idx = argsort(cum)

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=len(cum) + 1)
    count = 0
    while idx:
        n = cum[idx[-1]]
        li = []
        while idx and cum[idx[-1]] == n:
            li.append(idx.pop())
        for i in li:
            count += bit.sum(i)
        for i in li:
            bit.add(i, 1)
    # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
    # NH2 = (N+1)C2
    return count > (N + 1) * N // 2 / 2


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
# test(A)

indices = argsort(A)

# 座圧
B = compress(A)

lo = 0
hi = N
while abs(lo - hi) > 1:
    mid = (lo + hi) // 2
    if less_than(B[indices[mid]]):
        hi = mid
    else:
        lo = mid
print(A[indices[lo]])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


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


def test(A):
    N = len(A)
    M = []
    for l in range(N):
        for r in range(l + 1, N + 1):
            M.append(median(A[l:r]))
    print(median(M))


def less_than(k):
    arr = np.zeros(N + 1, dtype=int)
    arr[1:][B >= k] = 1
    arr[1:][B < k] = -1
    cum = arr.cumsum()
    idx = cum.argsort().tolist()
    cum = cum.tolist()

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=len(cum) + 1)
    count = 0
    while idx:
        n = cum[idx[-1]]
        li = []
        while idx and cum[idx[-1]] == n:
            li.append(idx.pop())
        for i in li:
            count += bit.sum(i)
        for i in li:
            bit.add(i, 1)
    # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
    # NH2 = (N+1)C2
    return count > (N + 1) * N // 2 / 2


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
A = np.array(A, dtype=int)
# test(A)

indices = A.argsort()

# 座圧
B = np.empty_like(A)
B[indices] = np.arange(N)

lo = 0
hi = N
while abs(lo - hi) > 1:
    mid = (lo + hi) // 2
    if less_than(B[indices[mid]]):
        hi = mid
    else:
        lo = mid
print(A[indices[lo]])

Submission status: Time Limit Exceeded

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

ans=0
m=[]
for i in range(N):
  for j in range(min(i+1,N-i)):
    m.append(A[i])
print(statistics.median_high(m))

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,N):
    m.append(statistics.median_high(A[i:j+1]))
print(statistics.median_high(m))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n == 1:
        print(a[0])
        return

    def merge(l, m, r):
        ll = [float('inf') for _ in range(m - l + 1)]
        for i in range(m - l):
            ll[i] = acca[l + i]
        rl = [float('inf') for _ in range(r - m + 1)]
        for i in range(r - m):
            rl[i] = acca[m + i]
        li, ri = 0, 0
        ret = 0
        for i in range(r - l):
            if ll[li] <= rl[ri]:
                acca[l + i] = ll[li]
                li += 1
            else:
                acca[l + i] = rl[ri]
                ri += 1
                ret += m - l - li
        return ret

    def merge_sort(l, r):
        if l + 1 >= r:
            return 0
        v1 = merge_sort(l, (l + r) // 2)
        v2 = merge_sort((l + r) // 2, r)
        v3 = merge(l, (l + r) // 2, r)
        return v1 + v2 + v3

    swap = ((n * (n - 1) // 2 + n) + 1) // 2
    low, high = 0, pow(10, 9) + 1
    while low < high:
        mid = (low + high) // 2
        acca = [0] + [1 if _a >= mid else -1 for _a in a]
        for i in range(n):
            acca[i + 1] += acca[i]
        
        if swap >= merge_sort(0, n + 1):
            low = mid + 1
        else:
            high = mid
    print(low - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cnt = 0
    for l, r in combinations(range(N+1),2):
        if C[l]<=C[r]:
            cnt += 1
    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
input = sys.stdin.buffer.readline
N = int(input())
a = list(map(int, input().split()))
b = [float("inf")] * N
l = [0] * N
r = [0] * N
c = [0] * N
h = [(v, i) for i, v in enumerate(a)]
asorted = [(v, i) for i, v in enumerate(a)]
asorted.sort()
heapq.heapify(h)
counter = 0
medi = N * (N + 1) // 4 + 1
#print(medi)
for _ in range(N):
  p, i = heapq.heappop(h)
  b[i] = p
  k = 0
  #print(b)
  for j in range(i - 1, -1, -1):
    m = max(abs(i - j) - 1, 0)
    if b[j] < b[i]:
      k += 1
    #print(k, m)
    if abs(m - k) <= 1 and k >= m:
      l[i] += 1
  k = 0
  for j in range(i + 1, N):
    m = abs(i - j) - 1
    if b[j] < b[i]:
      k += 1
    if abs(m - k) <= 1 and k >= m:
      r[i] += 1
#print(l, r)
for i in range(N):
  p, j = asorted[i]
  #print(p, j, counter)
  if counter + max(((l[j] + 1) * (r[j] + 1) - 1), 1) >= medi:
    print(p)
    break
  counter += max(((l[j] + 1) * (r[j] + 1) - 1), 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
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 inversion(a):
    "転倒してない数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        b.add(d[av], 1)
        ans += b.sum(d[av])
    return ans


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

    left = 0
    right = max(a)+1
    while right - left > 1:
        mid = (right + left)//2
        # acc = [0]*N
        # for i in range(N):
        #     if a[i] >= mid:
        #         acc[i] = acc[i-1]+1
        #     else:
        #         acc[i] = acc[i-1]-1
        acc = (1 if aa >= mid else -1 for aa in a)
        acc = tuple(accumulate(acc))
        invs = inversion(acc)
        if invs < (N*(N+1)//4 + 1):
            right = mid
        else:
            left = mid
    print(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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
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 inversion(a):
    "転倒してない数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        b.add(d[av], 1)
        ans += b.sum(d[av])
    return ans


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

    left = 0
    right = max(a)+1
    while right - left > 1:
        mid = (right + left)//2
        acc = [1 if aa >= mid else -1 for aa in a]
        acc = list(accumulate(acc))
        invs = inversion(acc)
        if invs < (N*(N+1)//4 + 1):
            right = mid
        else:
            left = mid
    print(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: Time Limit Exceeded

Solution code:
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1 = 0
        i2 = 0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt


n = int(input())
l = [int(_) for _ in input().split()]
p = (n*n+n)/2
q = 0
if p%2 == 0:
    q = p//2
else:
    q = p//2 + 1
l_set = list(set(l))
l_sorted = sorted(l_set)
ans = 0
l_t = [0 for _ in range(n)]
s = [0 for _ in range(n+1)]

low = 0
high = len(l_sorted) - 1


while low <= high:
    mid = (low + high) // 2
    m = l_sorted[mid]
    for j in range(n):
        if l[j] < m:
            l_t[j] = -1
        else:
            l_t[j] = 1
    for k in range(n):
        s[k+1] = s[k] + l_t[k]

    x = mergecount(s)
    if p-x >= q:
        low = mid+1
        ans = max(m,ans)
    else:
        high = mid-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1 = 0
        i2 = 0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt


n = int(input())
l = [int(_) for _ in input().split()]
p = (n*n+n)/2
q = 0
if p%2 == 0:
    q = p//2
else:
    q = p//2 + 1
l_set = list(set(l))
l_sorted = sorted(l_set)
ans = 0

low = 0
high = len(l_sorted) - 1


while low <= high:
    mid = (low + high) // 2
    m = l_sorted[mid]
    l_t = [0 for _ in range(n)]
    for j in range(n):
        if l[j] < m:
            l_t[j] = -1
        else:
            l_t[j] = 1
    s = [0 for _ in range(n+1)]
    for k in range(n):
        s[k+1] = s[k] + l_t[k]

    x = mergecount(s)
    if p-x >= q:
        low = mid+1
        ans = max(m,ans)
    else:
        high = mid-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(list(set(A)))

def f(x):
    B = [((x<=a)<<1)-1 for a in A]
    C = [N]
    [C.append(C[-1]+b) for b in B]

    r = 0
    Bit = [0] * (2*N+1)

    for i,c in enumerate(C):
        t=c-1
        while(t>0):
            r += Bit[t]
            t -= t&-t
        t=c-1
        while(t<=2*N+1):
            Bit[t] += 1
            t += t&-t
    return(r>=N*(N+1)//4)

l = 0
r = len(AS)-1
while l != r:
    if f(AS[(l+r+1)//2]):
        l = (l+r+1)//2
    else:
        r = (((l+r+1)//2)-1)
print(AS[r])