Problem:


Score : 700 points

Problem Statement

We will define the median of a sequence b of length M, as follows:

Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.

For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N.
For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a.
We will list m_{l, r} for all pairs (l, r) to create a new sequence m.
Find the median of m.

Constraints

1 \leq N \leq 10^5

a_i is an integer.

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the median of m.

Sample Input 1

3
10 30 20

Sample Output 1

30

The median of each contiguous subsequence of a is as follows:

The median of (10) is 10.

The median of (30) is 30.

The median of (20) is 20.

The median of (10, 30) is 30.

The median of (30, 20) is 30.

The median of (10, 30, 20) is 20.

Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.

Sample Input 2

1
10

Sample Output 2

10

Sample Input 3

10
5 9 5 9 8 9 3 5 4 3

Sample Output 3

8



Sample input:
3
10 30 20


Sample output:
30

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    M=max(A)

    def check(x):
        B=[1 if(a>=x) else -1 for a in A]
        S=[0]*(n+1)
        for i in range(n):
            S[i+1]=B[i]+S[i]

        # Sの転倒数を求める
        # coordinate compress
        D={d:i for i,d in enumerate(sorted(set(S)))}
        for i in range(n+1):
            S[i]=D[S[i]]

        # calculate
        cnt=0
        from operator import add
        bit=BIT([0]*(n+1),add,0)
        for i in range(n):
            s=bit.sum(S[i]+1)
            cnt+=s
            bit.add(S[i])

        return cnt*2>=n*(n+1)//2

    print(bisection(0,M,check))
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    M=max(A)

    def check(x):
        B=[1 if(a>=x) else -1 for a in A]
        S=[0]*(n+1)
        for i in range(n):
            S[i+1]=B[i]+S[i]

        # Sの転倒数を求める
        # coordinate compress
        D={d:i for i,d in enumerate(sorted(set(S)))}
        for i in range(n+1):
            S[i]=D[S[i]]

        # calculate
        cnt=0
        from operator import add
        bit=BIT([0]*(n+1),add,0)
        for i in range(n):
            s=bit.sum(S[i]+1)
            cnt+=s
            bit.add(S[i])

        return cnt*2>=n*(n-1)//2

    print(bisection(0,M+3,check))
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    M=max(A)

    def check(x):
        B=[1 if(a>=x) else -1 for a in A]
        S=[0]*(n+1)
        for i in range(n):
            S[i+1]=B[i]+S[i]

        # Sの転倒数を求める
        # coordinate compress
        D={d:i for i,d in enumerate(sorted(set(S)))}
        for i in range(n+1):
            S[i]=D[S[i]]

        # calculate
        cnt=0
        from operator import add
        bit=BIT([0]*(n+1),add,0)
        for i in range(n):
            s=bit.sum(S[i]+1)
            cnt+=s
            bit.add(S[i])

        return cnt*2>=n*(n-1)//2

    print(bisection(0,M,check))
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
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]"):

    def binary_search(x):

        def isOK(index):
            acc = (1 if aa >= index else -1 for aa in a)
            acc = tuple(accumulate(acc))
            invs = inversion(acc)
            return invs < (N*(N+1))//4 + 1

        ng = 0
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    ng, ok = binary_search(range(max(a)))
    print(ng)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
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: Wrong Answer

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

# n = 4
# A = [i+1 for i in range(n)]

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

print((n*(n+1))//(2*2))

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i+1] >= mid)
    bit = Bit(n+2)
    ans = 0

    #print("S OK")

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    #print("S OK2")
    #print(S)
    for i, p in enumerate(S):
        
        bit.add(p, 1)

        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く
        #print(i,ans)

    for i in range(n):
        if S[i] >= mid:
            ans += 1

    #print(le, ri, mid, ans)

    if ans >= (n*(n+1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)

Submission status: Wrong Answer

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

# n = 100000
# A = [1] * n

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

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i] >= mid)
    bit = Bit(n+2)
    ans = 0

    #print("S OK")

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    #print("S OK2")
    #print(S)
    for i, p in enumerate(S):
        bit.add(p, 1)
        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く

    #print(le, ri, mid, ans)

    if ans >= (n*(n-1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    if N&1:
        left = N//2 + 1
        right = N//2
    else:
        left = N//2
        right = N//2
    a_count = {}
    tmp = 1
    sum_ = 0
    for i in range(left):
        if a[i] in a_count:
            a_count[a[i]] += tmp
        else:
            a_count[a[i]] = tmp
        sum_ += tmp
        tmp += 2
    tmp = 2
    for i in range(N-1, N-1-right, -1):
        if a[i] in a_count:
            a_count[a[i]] += tmp
        else:
            a_count[a[i]] = tmp
        sum_ += tmp
        tmp += 2
    a_count = sorted(list(a_count.items()))
    # print(a_count)
    target = sum_ // 2 + 1
    tmp = 0
    for i in range(len(a_count)):
        tmp += a_count[i][1]
        if tmp > target:
            print(a_count[i][0])
            break
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    if N&1:
        left = N//2 + 1
        right = N//2
    else:
        left = N//2
        right = N//2
    a_count = {}
    tmp = 1
    sum_ = 0
    for i in range(left):
        if a[i] in a_count:
            a_count[a[i]] += tmp
        else:
            a_count[a[i]] = tmp
        sum_ += tmp
        tmp += 2
    tmp = 2
    for i in range(N-1, N-1-right, -1):
        if a[i] in a_count:
            a_count[a[i]] += tmp
        else:
            a_count[a[i]] = tmp
        sum_ += tmp
        tmp += 2
    a_count = sorted(list(a_count.items()))
    # print(a_count)
    target = sum_ // 2 + 1
    tmp = 0
    for i in range(len(a_count)):
        tmp += a_count[i][1]
        if tmp >= target:
            print(a_count[i][0])
            break
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

a_sorted = sorted(a)
import math

a_max = a_sorted[-1]
inf = a_sorted[0]
if len(a)==1:
  x = a_max
else:
  x = a_sorted[n//2+1]
  
while x > inf and x < a_max:
  
  b = []
  for i in range(n):
    if a[i] >= x:
      b.append(1)
    else:
      b.append(-1)
  
  c = [0]
  s = 0
  for i in range(n):
    s += b[i]
    c.append(s)
    
  m = min(c)
  M = max(c)
  tree = [0 for i in range(M - m + 1)]
  cnt = 0
  for i in range(n):
    for j in range(c[i] - m + 1):
      cnt += tree[j]
    tree[c[i] - m] += 1
    
  if cnt >= n / 2:
    inf = x
    x += math.ceil((a_max - x) / 2)
  else:
    x -= math.ceil((x - inf) / 2)
    
print(x)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n = int(input())
a = list(map(int, input().split()))
c = [(v, (n-i)*(i+1)) for i, v in enumerate(a)]
c.sort(key=itemgetter(0))
p = n*(n+1)*(n+2)//6
s = 0
for v, m in c:
    if s >= p//2 :
        print(v)
        break
    else :
        s += m

Submission status: Wrong Answer

Solution code:
n,a=open(0);print(a.split()[(int(n)-1)//2])

Submission status: Wrong Answer

Solution code:
N = int(input())
AA = list(map(int, input().split()))
A = [0] * N
odd = N % 2
middleIndex = (N + 1) // 2
ansIndex = (N * (N+1) // 2) // 2 + 1

for i in range(N) :
    A[i] = (i+1, AA[i])

A.sort(key=lambda X : X[1])

def weight(index) :  # 出現回数
    if index <= middleIndex :
        return index * 2 - 1
    else :
        return (N - index + 1) * 2


count = 0
for index, value in A :
    count += weight(index)
    if count >= ansIndex :
        print(value)
        break

Submission status: Wrong Answer

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

odd = N % 2

if N == 1 :
    print(A[0])
else :
    middleIndex = ((N * (N+1)) // 2) // 2 + 1
    count = 0
    for i in range(1, N+1) :
        if count + (i // 2) * 2 + 1 > middleIndex :
            R = middleIndex - count + 1  # 部分列の長さ, 中心i
            B = A[i - 1 - R//2 - 1 - odd : i - 1 + R//2]
            B.sort()
            print(B[R // 2])
            break
        count += (i // 2) * 2 + 1

Submission status: Wrong Answer

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

if N == 1 :
    print(A[0])
else :
    middleIndex = ((N * (N+1)) // 2) // 2 + 1
    count = 0
    for i in range(1, N+1) :
        if count + (i // 2) * 2 + 1 > middleIndex :
            R = middleIndex - count + 1  # 部分列の長さ, 中心i
            B = A[i - 1 - R//2 - 1 : i - 1 + R//2]
            B.sort()
            print(B[R // 2])
            break
        count += (i // 2) * 2 + 1

Submission status: Wrong Answer

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

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

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

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

    def range_sum_oc(self, i, j):#(i:j]
        if i == 1:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def range_sum_cc(self, i, j):#[i:j]
        if i == 1:
            return self.sum(j)
        return self.sum(j) - self.sum(i - 1)

def f(x):
    s = n
    bit = Bit(2 * n + 1)
    judge = 0
    for ai in a:
        if ai >= x:
            s += 1
        else:
            s -= 1
        bit.update(s, 1)
        judge += bit.sum(s)
        if judge >= n_sub_half:
            return 1
    return 0

b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m + 1
    else:  # ans < x
        r = m

print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2 + 1) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m + 1
    else:  # ans < x
        if f(b[m - 1]):
            m = m - 1
            break
        else:
            r = m - 2


print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2 + 1
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m + 1
    else:  # ans < x
        if f(b[m - 1]):
            m = m - 1
            break
        else:
            r = m - 2


print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m + 1
    else:  # ans < x
        if f(b[m - 1]):
            m = m - 1
            break
        else:
            r = m - 2


print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m
    else:  # ans < x
        r = m - 2


print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m
    else:  # ans < x
        r = m


print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m + 1
    else:  # ans < x
        r = m - 1


print(b[m])

Submission status: Wrong Answer

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


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 f(x):  # 連続部分列の中央値がｘなる場合の数
    s = Bit(2)
    S = Bit(2 * n + 1)
    judge = 0
    for p in a:
        s.add((p >= x) + 1, 1)
        b = n + s.tree[2] - 2 * s.tree[1]
        S.add(b,1)
        judge += S.sum(b)
        if judge >= n_sub_half:
            return 1
    return 0


b = sorted(set(a))
l, r = 0, len(b)
n_sub_half = (n * (n + 1) // 2) // 2
while True:
    m = (r + l) // 2
    if f(b[m]):  # ans >= x
        if m == len(b) - 1:
            break
        elif not f(b[m + 1]):
            break
        else:
            l = m + 1
    else:  # ans < x
        r = m


print(b[m])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

N = int(input())
A = np.array(input().split(), dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  cnt_below = 0
  memo = defaultdict(int)
  result = 0
  current = 0
  for a in A:
    if a > x:
      current += 1
      cnt_below += memo[current]
    else:
      cnt_below -= memo[current]
      current -= 1
    cnt_below += 1
    memo[current] += 1
    result += cnt_below
  return result <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array(input().split(), dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  cnt_below = 0
  memo = [0] * (2*N+1)
  result = 0
  current = 0
  for a in A:
    if a > x:
      current += 1
      cnt_below += memo[current]
    else:
      cnt_below -= memo[current]
      current -= 1
    cnt_below += 1
    memo[current] += 1
    result += cnt_below
  return result <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import defaultdict
N = int(input())
a = list(map(int,input().split()))
d = defaultdict(lambda:0)

for i in range(N):
    if i <= ceil(N/2)-1:
        d[a[i]] += 2*i+1
    else:
        d[a[i]] += 2*(N-i)

a = list(set(a))
a.sort()
M = (N*(N+1))//2

m = 0
for i in range(N):
    m += d[a[i]]
    if m >= M//2+1:
        print(a[i])
        break

Submission status: Wrong Answer

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

def f(n):
    l = n + 1
    r = N - n
    return min(l, r) + min(l, r + 1) - 1

D = dict()

for i in range(N):
    tmp = D.get(A[i], 0)
    D[A[i]] = tmp + f(i)

VK = list(D.items())
VK.sort()

idx = (N * (N + 1) // 2) // 2
i = 0
for v, cnt in VK:
    # print("i:{}, v:{},cnt:{}, idx:{}".format(i, v, cnt, idx))
    i += cnt
    if i > idx:
        print(v)
        break

Submission status: Wrong Answer

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

def f(n):
    l = n + 1
    r = N - n
    return min(l, r) + min(l, r + 1) - 1

D = dict()

for i in range(N):
    tmp = D.get(A[i], 0)
    D[A[i]] = tmp + f(i)

VK = list(D.items())
VK.sort()

idx = (N * (N + 1) // 2) // 2 
i = 0
for v, cnt in VK:
    # print("i:{}, v:{},cnt:{}, idx:{}".format(i, v, cnt, idx))
    i += cnt
    if i >= idx:
        print(v)
        break

Submission status: Wrong Answer

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

def f(n):
    l = n + 1
    r = N - n
    return min(l, r) + min(l, r + 1) - 1

D = dict()

for i in range(N):
    tmp = D.get(A[i], 0)
    D[A[i]] = tmp + f(i)

VK = list(D.items())
VK.sort()

idx = (N * (N + 1) // 2) // 2 + 1
i = 0
for v, cnt in VK:
    # print("i:{}, v:{},cnt:{}, idx:{}".format(i, v, cnt, idx))
    i += cnt
    if i >= idx:
        print(v)
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs) - 1

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            bit.add(s + n, 1)
            ret += bit.sum(s + n - 1)
        return ret

    while lo < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid + 1
        else:
            hi = mid
    return xs[lo]


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

if __name__ == '__main__':
    main()