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():
    N, *A = map(int, open(0).read().split())

    offset = 10 ** 5
    size = 2 * offset + 5

    def check(x):
        def bit_sum(i):
            s = 0
            while i > 0:
                s += bit[i]
                i -= i & -i
            return s

        def bit_add(i, x):
            while i <= size:
                bit[i] += x
                i += i & -i

        global bit
        bit = [0] * (size + 1)

        sm = tot = 0
        bit_add(offset, 1)
        for a in A:
            tot += 1 if x <= a else -1
            sm += bit_sum(offset + tot)
            bit_add(offset + tot, 1)

        return ((N * (N + 1) // 2 + 1) // 2 <= sm)


    ok, ng = 0, 10 ** 9 + 5
    while ok + 1 != ng:
        md = (ng + ok) // 2
        if check(md):
            ok = md
        else:
            ng = md

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    offset = 10 ** 5
    size = offset * 2 + 5

    N, *A = map(int, open(0).read().split())


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

    def bit_add(i, x):
        while i <= size:
            bit[i] += x
            i += i & -i

    def check(x):
        global bit
        bit = [0] * size

        sm = tot = 0
        bit_add(offset, 1)
        for a in A:
            tot += 1 if x <= a else -1
            sm += bit_sum(offset + tot)
            bit_add(offset + tot, 1)

        return ((N * (N - 1) // 2 + N + 1) // 2 <= sm)


    ok, ng = 0, 10 ** 9 + 5
    while ok + 1 != ng:
        md = (ng + ok) // 2
        if check(md):
            ok = md
        else:
            ng = md

    print(ok)


if __name__ == '__main__':
    main()

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, *A = map(int, open(0).read().split())

offset = 10 ** 5

def check(x):
    bit = BIT(offset * 2 + 5)

    sm = tot = 0
    bit.add(offset, 1)
    for a in A:
        tot += 1 if x <= a else -1
        sm += bit.sum(offset + tot)
        bit.add(offset + tot, 1)

    return ((N * (N - 1) // 2 + N + 1) // 2 <= sm)


ok, ng = 0, 10 ** 9 + 5
while ok + 1 != ng:
    md = (ng + ok) // 2
    if check(md):
        ok = md
    else:
        ng = md

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
a = list()
for elem in input().split(' '):
    a.append(int(elem)) 

def median(lr):
    lr.sort()
    index = len(lr)//2
    return lr[index]

b = list()
for l,r in list(itertools.combinations(range(N+1), 2)):
        b.append(median(a[l:r]))
b.sort()  
print(median(b))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list()
for elem in input().split(' '):
    a.append(int(elem)) 

def median(lr):
    lr.sort()
    index = len(lr)//2
    return lr[index]

b = list()
for l in range(N):
    for r in range(l+1,N+1):
        b.append(median(a[l:r]))
b.sort()  
print(median(b))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(item) for item in input().split()]
a_sorted = sorted(a)

def can_be_midofmid(b):
    high_low_cum = [0] * (n + 1)
    for i, item in enumerate(a):
        if item >= b:
            high_low_cum[i+1] = 1
        else:
            high_low_cum[i+1] = -1
    for i in range(n):
        high_low_cum[i+1] += high_low_cum[i]
    bit_n = 1 << n.bit_length()
    bit = [0] * (bit_n+1)

    def bit_add(x, w):
        while x <= bit_n:
            bit[x] += w
            x += x & -x

    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= x & -x
        return ret

    val = 0
    dic = dict(zip(sorted(high_low_cum), [item for item in range(len(high_low_cum))]))
    for i, item in enumerate(high_low_cum):
        val += bit_sum(dic[item] + 1)
        bit_add(dic[item] + 1, 1)
    return val  >= ((n+1) * n + 2)// 4  

l = -1; r = n
while r - l > 1:
    mid = (r + l) // 2
    if can_be_midofmid(a_sorted[mid]):
        l = mid
    else:
        r = mid
print(a_sorted[r-1])

Submission status: Time Limit Exceeded

Solution code:
class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    #合計値
    return l + r
  def add(self, x, v):
    k = x + self.N - 1
    self.T[k] += v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] += v
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

def judge(x, a):
  N = len(a)
  v = [0] * (N + 1)
  mi = 0
  ma = 0
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)
    mi = min(mi, v[i + 1])
    ma = max(ma, v[i + 1])

  b = segTree(ma - mi + 1)
  Ans = 0
  ge = b.getV
  ad = b.add
  for i in v:
    Ans += ge(0, i - mi)
    ad(i - mi, 1)
  return Ans >= N * (N + 1) / 4

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

  b = list(set(a))
  b.sort()

  ok = 0
  ng = len(b)
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid], a):
      ok = mid
    else:
      ng = mid

  print(b[ok])

main()

Submission status: Time Limit Exceeded

Solution code:
class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    #合計値
    return l + r
  def add(self, x, v):
    k = x + self.N - 1
    self.T[k] += v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] += v
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

def nibutan(x, a, b):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid], a):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x, a):
  N = len(a)
  v = [0] * (N + 1)
  mi = 0
  ma = 0
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)
    mi = min(mi, v[i + 1])
    ma = max(ma, v[i + 1])

  b = segTree(ma - mi + 1)
  Ans = 0
  for i in v:
    Ans += b.getV(0, i - mi)
    b.add(i - mi, 1)
  return Ans >= N * (N + 1) / 4

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

  b = list(set(a))
  b.sort()

  print(b[nibutan(len(b), a, b)])

main()

Submission status: Time Limit Exceeded

Solution code:
class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    #合計値
    return l + r
  def add(self, x, v):
    k = x + self.N - 1
    self.T[k] += v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] += v
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

def nibutan(x, a, b):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid], a):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x, a):
  N = len(a)
  v = [0] * (N + 1)
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)

  mi = min(v)
  ma = max(v)
  u = [0] * (N + 1)
  for i in range(N + 1):
    u[i] = v[i] - mi

  b = segTree(ma - mi + 1)
  Ans = 0
  for i in range(len(u)):
    Ans += b.getV(0, u[i])
    b.add(u[i], 1)
  return Ans >= N * (N + 1) / 4

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

  b = list(set(a))
  b.sort()

  print(b[nibutan(len(b), a, b)])

main()

Submission status: Time Limit Exceeded

Solution code:
import math

class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    #合計値
    return l + r
  def set(self, L):
    for i in range(len(L)):
      self.update(i, L[i])
  def add(self, x, v):
    k = x + self.N - 1
    self.T[k] += v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] += 1
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

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

b = list(set(a))
b.sort()
def nibutan(x):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x):
  v = [0] * (N + 1)
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)

  mi = min(v)
  ma = max(v)
  u = [0] * (N + 1)
  for i in range(N + 1):
    u[i] = v[i] - mi

  b = segTree(ma - mi + 1)
  Ans = 0
  for i in range(len(u)):
    Ans += b.getV(0, u[i])
    b.add(u[i], 1)
  return Ans >= N * (N + 1) / 4

print(b[nibutan(len(b))])

Submission status: Time Limit Exceeded

Solution code:
import math

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

b = list(set(a))
b.sort()
def nibutan(x):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x):
  v = [0] * (N + 1)
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)

  mi = min(v)
  ma = max(v)
  u = [0] * (N + 1)
  for i in range(N + 1):
    u[i] = v[i] - mi

  b = BIT(ma - mi + 1)
  Ans = 0
  for i in range(len(u)):
    Ans += b.get(0, u[i])
    b.add(u[i], 1)
  return Ans >= N * (N + 1) / 4

class BIT():
  def __init__(s, k):
    s.N = k
    s.L = math.ceil(math.log(s.N - 1, 2) + 1)
    s.P = [1] * (s.L + 1)
    for i in range(1,s.L + 1):
      s.P[i] = s.P[i - 1] * 2
    s.K = s.P[-1] * 2
    s.T = [0] * s.K
    
  def get(s, l, r):
    return s.get_sub(l, r, 0, s.P[s.L] - 1, 0, 0)

  def get_sub(s, l, r, ml, mr, x, id):
    if ml >= l and r >= mr:
      return s.T[s.P[x] + id]
    if mr < l or r < ml:
      return 0
    Ans = s.get_sub(l, r, ml, (mr + ml - 1) // 2, x + 1, id * 2)
    Ans += s.get_sub(l, r, (mr + ml + 1) // 2, mr, x + 1, id * 2 + 1)
    return Ans

  def add(s, n, p):
    s.add_sub(n, p, s.L)

  def add_sub(s, n, p, x):
    s.T[s.P[x] + n] += p
    if x != 0:
      s.add_sub(n // 2, p, x - 1)

print(b[nibutan(len(b))])

Submission status: Time Limit Exceeded

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


lb = -1
rb = 10**9 + 10
# check(x) == Trueとなる最小のx
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)

Submission status: Time Limit Exceeded

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


def check(x):
    class SegmentTree():
        """
            Parameters
            ----------
            array : list
                to construct segment tree from
            f : func
                binary operation of the monoid
            e : 
                identity element of the monoid
            size : int
                limit for array size
        """

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

        def build(self):
            dat, n, f = self.dat, self.n, self.f
            for i in range(n - 1, 0, -1):
                dat[i] = f(dat[i << 1], dat[i << 1 | 1])

        def modify(self, p, v):
            """
            set value at position p (0-indexed)
            """
            f, n, dat = self.f, self.n, self.dat
            p += n
            dat[p] = v
            while p > 1:
                dat[p >> 1] = f(dat[p], dat[p ^ 1])
                p >>= 1

        def query(self, l, r):
            """
            result on interval [l, r) (0-indexed)
            """
            f, e, n, dat = self.f, self.e, self.n, self.dat
            res = e
            l += n
            r += n
            while l < r:
                if l & 1:
                    res = f(res, dat[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = f(res, dat[r])
                l >>= 1
                r >>= 1
            return res

    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]
    e = 0
    size = 2 * N + 10
    ST = SegmentTree([e] * size, f=lambda x, y: x + y, e=e, size=size)
    count = 0
    for c in cumsum:
        c += N + 5
        count += ST.query(0, c + 1)
        ST.modify(c + 1, ST.query(c + 1, c + 2) + 1)
    return 2 * count > N * (N + 1) // 2


lb = -1
rb = 10**9 + 10
# check(x) == Trueとなる最小のx
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)

Submission status: Time Limit Exceeded

Solution code:
def calcMedian(unsortedList):
    sortedList = sorted(unsortedList)
    return sortedList[(len(sortedList) // 2)]

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

m = []
for l in range(1, n+1):
    for r in range(l, n+1):
        m.append(calcMedian(b[l-1:r]))

print(calcMedian(m))

Submission status: Time Limit Exceeded

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.add(sum_+geta, 1)

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

Submission status: Time Limit Exceeded

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 ordered(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]"):

    # print(N)
    # print(*a)
    # print("")
    cand = sorted(a)
    # 2分探索
    left = 0
    right = len(a)
    counter = 0
    while left + 1 != right:        # [left, right)
        # if counter == 10:
        #     break
        counter += 1
        xi = left + (right-left)//2
        x = cand[xi]
        t = [+1 if x <= av else -1 for av in a]
        S = list(accumulate(t))
        invs = ordered(S)
        # print("x: {}".format(x), "[{},{})".format(left, right))
        # print("t: {}".format(t))
        # print("S: {}".format(S), "=> ", invs)
        # print("ceil", math.ceil((N*(N+1)/2)/2))
        if invs >= math.ceil((N+1)*N/2/2):
            if left == xi:
                break
            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()


# BITでやればいいって、びびっときました

# あるxに対して、数列bの各要素を置き換える。
# 要素がx以上なら+1へ。そうでないなら-1へ。
# そうしてできた数列をaとする。
# aの連続部分列 a[l, r] (1<=l<=r<=N)のうち、
# 要素の総和が0以上のものはいくつか

# あるxに対して、数列bの各要素を置き換える。
# 要素がx以上なら+1へ。そうでないなら-1へ。
# そうしてできた数列をaとする。
# aの先頭から要素iまでの累積和からなる数列をSとする
# (l, r) (1<=l<=r<=N)のうち、S[l]<=S[r]を満たすものの数が、
# math.ceil(((N+1)*N/2)/2)よりも大きいものの中で最大のx

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
alist=list(map(int,input().split()))
numdict={}
amount=0
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()

newmedilist=[]
for i in range(1,N):
  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: Time Limit Exceeded

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

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
def invnum(n,a):
    bit=Bit(n)
    res=0
    for j in range(n):
        res+=j-bit.sum(a[j])
        bit.add(a[j],1)
    return res
N=int(input())
A=[int(i) for i in input().split()]
def solve(x):
    S=[0 for i in range(N+1)]
    for i in range(N):
        if A[i]<x:
            S[i+1]=S[i]-1
        else:
            S[i+1]=S[i]+1
    T=[seq[1]+1 for seq in sorted([(S[i],i) for i in range(N+1)])]
    return invnum(N+1,T)
low=1
high=max(A)+1
M=(N*(N+1))//2
while(high-low>1):
    mid=(low+high)//2
    if solve(mid)*2<=M:
        low=mid
    else:
        high=mid
print(low)

Submission status: Time Limit Exceeded

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

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	# あとで全体を-min_tmp+1だけ足さないとバグる
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)

Submission status: Time Limit Exceeded

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

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
def invnumber(n,A):
  S=[0]*n
  A=sorted([(A[i],i) for i in range(n)])
  for i in range(1,n):
     S[A[i][1]]=i
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=S[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs
  
def Check(x):
  S=[0]
  for i in range(N):
    if A[i]>sorted_A[x]:
      S.append(S[-1]+1)
    else:
      S.append(S[-1]-1)
  return invnumber(N+1,S)
      
l,r=0,N-1
while l<r:
  m=(l+r)//2
  if Check(m)>(N*(N+1)//4):
    r=m
  else:
    l=m+1
print(sorted_A[l])

Submission status: Time Limit Exceeded

Solution code:
class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(i):
    x = vals[i]
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
vals = sorted(set(L))
print(vals[paramin(medleq, 0, len(vals)-1)])

Submission status: Time Limit Exceeded

Solution code:
class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(x):
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
print(paramin(medleq, min(L), max(L)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = []
    for l in range(0, len(a)):
        for r in range(l+1, len(a)+1):
            m.append(a[l:r][len(a[l:r])//2])
    m.sort()
    if len(m) == 1:
        print(m[len(m)//2])
    else:
        print(m[len(m)//2+1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class BIT():
    def __init__(self,length):
        self.length = length
        self.values = [0 for _ in range(length+1)]
    
    def add(self,location,value):
        x = location
        while x < self.length + 1:
            self.values[x] += value
            x += x & -x
    
    def sum(self,right):
        x = right
        answer = 0
        while x > 0:
            answer += self.values[x]
            x -= x & -x
        return(answer)

def judge(x):
    bit = BIT(2*N + 1)
    bit.add(N+1,1)
    cumsum = 0
    validNum = 0
    interval = N*(N+1)//2
    lowbound = interval - interval//2
    for i in range(N):
        if a[i] >= x:
            cumsum += 1
        else:
            cumsum -= 1
        validNum += bit.sum(cumsum+N+1)
        bit.add(cumsum+N+1,1)
    return(validNum >= lowbound)    
    
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:
import copy


def quick_sort(array, left, right):
    if left >= right:
        return
    low = left
    high = right
    key = array[low]
    while left < right:
        while left < right and array[right] >= key:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] <= key:
            left += 1
        array[right] = array[left]
    array[right] = key    # 最后的key为什么会落在right上呢？
    quick_sort(array, low, left - 1)
    quick_sort(array, left + 1, high)


N = int(input().strip())
nums = list(map(int, input().strip().split()))
nums_length = len(nums)
if nums_length == 1:
    print(nums[0])
else:
    median = []
    subarray = []
    for i in range(nums_length):
        subarray.append(nums[i])
        subarray_length = len(subarray)
        if subarray_length == 1:
            key = subarray[0]
            median.append(key)
        else:
            for k in range(subarray_length - 2, -1, -1):
                if subarray[k] > nums[i]:
                    subarray[k + 1] = subarray[k]
                    if k == 0:
                        subarray[0] = nums[i]
                        break
                else:
                    subarray[k + 1] = nums[i]
                    break
            key = subarray[subarray_length // 2]
            median.append(key)
            temp = copy.deepcopy(subarray)
            for j in range(len(subarray) - 1):
                temp.remove(nums[j])
                key = temp[len(temp) // 2]
                median.append(key)
    quick_sort(median, 0, len(median) - 1)
    print(median[len(median) // 2])

Submission status: Time Limit Exceeded

Solution code:
import copy

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