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: Accepted

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


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+2)
    update(bit, n+1, 1)
    ans = 0
    for v in cumsum:
        ans += query(bit, v+n+1)
        update(bit, n+v+1, 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: Accepted

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

def median(num):
    row=[0]*N
    for i in range(N):
        if A[i]>num:
            row[i]=1
        else:
            row[i]=-1
    m=0
    data=[0]
    for i in range(0,N):
        data.append(data[-1]+row[i])
        m=min(m,data[i+1])
    data=[data[i]-m+1 for i in range(N+1)]
    ans=0
    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**9
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)

Submission status: Accepted

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

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1

def check(x):
  b = [0] * N
  for i in range(N):
    if a[i] <= x: b[i] = -1
    else: b[i] = 1
  cs = [0] * (N + 1)
  for i in range(N): cs[i + 1] = cs[i] + b[i]
  mn = -min(cs) + 1
  fwk = BIT(N + 1)
  k = 0
  for i in range(N + 1):
    k += fwk.sum(cs[i] + mn)
    fwk.add(cs[i] + mn, 1)
  #print(k)
  return k < N * (N + 1) // 4


ok = max(a)
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
sortA=sorted(set(a))+[float('inf')]
def isOK(m):
  x=sortA[m]
  count=[0]*(2*n+1)
  count[n+1]=1
  i=n+1
  s=1
  res=0
  for b in a:
    if b>=x:
      i+=1
      s+=count[i]
    else:
      s-=count[i]
      i-=1
    res+=s
    count[i]+=1
    s+=1
  if res>=n*(n+1)//4:
    return False
  else:
    return True
l=0
r=len(sortA)-1
while r>l+1:
  mid=(r+l)//2
  if isOK(mid):
    r=mid
  else:
    l=mid
print(sortA[l])

Submission status: Accepted

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


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    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, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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


def solve(val):
    val = a_sorted[val]
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(a_sorted[ok])

Submission status: Accepted

Solution code:

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


def updiv(a,b):
    if a % b == 0:
        return a//b
    else:
        return a//b +1

def want(x):

    lis = []
    for i in a:
        if i >= x:
            lis.append(1)
        else:
            lis.append(-1)

    slis = [0]
    for i in lis:
        slis.append(slis[-1] + i)

    #座圧する(1-Originにすべき)
    dic = {}
    nlis = []
    for i in slis:
        if i not in dic:
            dic[i] = None
            nlis.append(i)
    nlis.sort()
    for i in range(len(nlis)):
        dic[nlis[i]] = i+1

    #print (x,dic)
    
    ans = 0
    BIT = [0] * (len(nlis) + 1)

    for i in slis:
        j = dic[i]

        ans += bitsum(j,BIT)
        bitadd(j,1,BIT)
        
    #print (x,ans,slis)
    return ans
    

N = int(input())

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

l = 1
r = max(a) + 1

while r-l != 1:

    m = (l+r) // 2

    mnum = want(m)

    if mnum >= updiv((N**2+N)//2,2):
        l = m
    else:
        r = m

print (l)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    f = list(set(a))
    f.sort()
    c = [bisect.bisect_left(f,i) for i in a]
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = len(f)
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in c]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+1 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print(f[l])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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 + min_i)//2, index

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: Accepted

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

sortA = sorted(set(A)) + [float('inf')]

def isOk(n):
    x = sortA[n]
    count = [0 for _ in range(2 * N + 1)]
    count[N + 1] = 1

    i = N + 1
    s = 1
    result = 0

    for a in A:
        if a >= x:
            i += 1
            s += count[i]
        else:
            s -= count[i]
            i -= 1
        result += s
        count[i] += 1
        s += 1

    if result >= N * (N + 1) // 4:
        return False
    else:
        return True


left = 0
right = len(sortA) - 1

while right - left > 1:
    mid = (left + right ) // 2

    if isOk(mid):
        right = mid
    else:
        left = mid

print(sortA[left])

Submission status: Accepted

Solution code:
class BIT(object):
    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)


def main():
    n = int(input())
    *a, = map(int, input().split())
    small, large = 0, max(a)
    criteria = n * (n + 1) // 4

    while large - small > 1:
        mid = (small + large) // 2
        num = 0
        b = BIT(2 * n + 1)
        suma = 0
        b.add(suma + n + 1, 1)
        for aa in a:
            suma += 1 if aa <= mid else -1
            num += b.sum(suma + n)
            b.add(suma + n + 1, 1)

        if num > criteria:
            large = mid
        else:
            small = mid
    print(large)


main()

Submission status: Accepted

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)
        """
        self.add(p, self.fi(v, self.array[p]))
    
    def add(self, p, dv):
        """
        add value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        array[p] = f(array[p], dv)
        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(c + 1)
        BIT.add(c + 1, 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(A_sorted[rb])

Submission status: Accepted

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


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


e = 0
size = 2 * N + 2
f = lambda a, b: a + b
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]
    ST = SegmentTree([e] * size, f=f, e=e, size=size)
    count = 0
    for c in cumsum:
        c += offset
        count += ST.query(0, c + 1)
        ST.modify(c + 1, ST.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(A_sorted[rb])

Submission status: Accepted

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


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(A_sorted[rb])

Submission status: Accepted

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(A_sorted[rb])

Submission status: Accepted

Solution code:
import math
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 >= math.ceil(n*(n+1)//4):
        left = mid
    else:
        right = mid
print(a_sorted[left])

Submission status: Accepted

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)

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

Submission status: Accepted

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

a_sorted = sorted(set(a))+[10**18]
left, right = 0, len(a_sorted)-1

while right-left > 1:
    mid = (left+right)//2
    x = a_sorted[mid]

    count = [0]*(2*n+1)
    count[n+1] = 1
    i, accum, res = n+1, 1, 0

    for aa in a:
        if aa >= x:
            i += 1
            accum += count[i]
        else:
            accum -= count[i]
            i -= 1

        res += accum
        count[i] += 1
        accum += 1

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

print(a_sorted[left])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        
    def node_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
            
        return s
    
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += (i & -i)
            
    def reset(self):
        self.tree = [0] * (self.size + 1)
        
        
n = ni()
a = list(li())

t = n*(n+1) // 4
alt = sorted(set(a))

l,r = 0, len(alt) - 1
bitree = BIT(n*2)

while l <= r:
    m = (l+r) // 2
    am = alt[m]
    acc = accumulate(1 if ai-am >= 0 else -1 for ai in a)
    bitree.add(n,1)
    right_order = 0
    
    for p in acc:
        p += n
        right_order += bitree.node_sum(p)
        bitree.add(p, 1)
        
    if right_order >= t:
        l = m+1
    else:
        r = m-1
        
    bitree.reset()
    
print(alt[r])

Submission status: Accepted

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):
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=A[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: Accepted

Solution code:
# D

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

def search(c):
    bar = N
    r = 0
    res_nega = 0
    dp_arr = [0]*(2*N+1)
    
    for i in range(N):
        dp_arr[bar] += 1
        if a_list[i] < c:
            r += dp_arr[bar]
            bar += 1
        else:
            r -= (dp_arr[bar-1])
            bar -= 1
        
        res_nega += r
    return res_nega

# binary search
a_sorted = sorted(a_list)

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

while True:
    if search(a_sorted[mid]) <= C // 2:
        if mid == N-1:
            break
        elif search(a_sorted[mid+1]) > C // 2:
            break
        else:
            left = mid
            mid = (mid + right) // 2
    else:
        right = mid + 1
        mid = (mid + left) // 2
        
print(a_sorted[mid])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
A_sorted = sorted(A)


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

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(2 * N + 1)  # N+1番目が真ん中
target = (N * (N+1) // 2 + 1) // 2

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

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

    BIT.reset()

    inversion = 0

    for j in range(N):
        inversion += BIT.sum(Binary[j] + N + 1) + (Binary[j] >= 0)
        BIT.add(Binary[j] + N + 1, 1)

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

print(r)

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
A_sorted = sorted(A)


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

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

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

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(2 * N + 1)  # N+1番目が真ん中
target = (N * (N+1)) // 4

# にぶたん
l, r = -1, 10**9+1
if N == 1:
    print(A[0])
    exit()
while r - l > 1:
    X = (r + l) // 2
    Binary = [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    inversion = 0

    for j in range(N):
        inversion += BIT.sum(Binary[j] + N + 1) + (Binary[j] >= 0)
        BIT.add(Binary[j] + N + 1, 1)

    #print(X, inversion, Binary)
    if inversion >= target:
        l = X
    else:
        r = X

#print(X, inversion)
print(r)