Problem:


Score : 600 points

Problem Statement

There is a function f(x), which is initially a constant function f(x) = 0.

We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:

An update query 1 a b: Given two integers a and b, let g(x) = f(x) + |x - a| + b and replace f(x) with g(x).

An evaluation query 2: Print x that minimizes f(x), and the minimum value of f(x). If there are multiple such values of x, choose the minimum such value.

We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.

Constraints

All values in input are integers.

1 \leq Q \leq 2 \times 10^5

-10^9 \leq a, b \leq 10^9

The first query is an update query.

Input

Input is given from Standard Input in the following format:

Q
Query_1
:
Query_Q

See Sample Input 1 for an example.

Output

For each evaluation query, print a line containing the response, in the order in which the queries are given.

The response to each evaluation query should be the minimum value of x that minimizes f(x), and the minimum value of f(x), in this order, with space in between.

Sample Input 1

4
1 4 2
2
1 1 -8
2

Sample Output 1

4 2
1 -3

In the first evaluation query, f(x) = |x - 4| + 2, which attains the minimum value of 2 at x = 4.

In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6, which attains the minimum value of -3 when 1 \leq x \leq 4. Among the multiple values of x that minimize f(x), we ask you to print the minimum, that is, 1.

Sample Input 2

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

Sample Output 2

-1000000000 3000000000



Sample input:
4
1 4 2
2
1 1 -8
2


Sample output:
4 2
1 -3

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


from bisect import bisect_left, bisect_right, insort_left
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = array('q',
                         sorted(ls))  # insertを爆速にするためにarray型にします。signed long long 前提です

    # def __repr__(self):
    #     return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        # idx = self.bisect_left(x)
        # self.bst.insert(idx,x)
        insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc127/tasks/abc127_f
# bとaを別で考えれば簡単、いままで出てきたAの中央値がxだしね

# とりあえずf(x)のxを出力するプログラムを作成してからどうやって計算量を削減するか考える

Q = read_a_int()
# 中央値

com, a, b = read_ints()
b_sum = b
A = BinarySearchTree([a])


def f(x, A, b_sum):
    ret = b_sum
    for a in A:
        ret += abs(a - x)
    return ret


for _ in range(Q - 1):
    com, *tmp = read_ints()
    if com == 1:
        a, b = tmp
        b_sum += b
        A.insert(a)
    else:
        x = A[(len(A) - 1) // 2]
        print(x, f(x, A, b_sum))

Submission status: Time Limit Exceeded

Solution code:
import heapq

Q = int(input())
m = L = R = 0
l, r = [], []
n = 0
b = 0

for i in range(Q):
  query = list(map(int, input().split()))
  if len(query) == 3: # 更新クエリ
    b += query[2]
    new = query[1]
    if  n == 0:
      m = new
    elif n == 1:
      if new <= m:
        heapq.heappush(l, -new)
        heapq.heappush(r, m)
        L, R = new, m
        m = new
      else:
        heapq.heappush(l, -m)
        heapq.heappush(r, new)
        L, R = m, new
    elif n == 2:
      if new < m:
        m = -heapq.heappop(l)
        heapq.heappush(l, -new)
        L = new
      else:
        _r = heapq.heappop(r)
        if new < _r:
          m = new
          heapq.heappush(r, _r)
        else:
          m = _r
          heapq.heappush(r, new)
          R = new
    else:
      _l = - heapq.heappop(l)
      _r = heapq.heappop(r)
      if n%2:
        if new <= _l:
          heapq.heappush(l, -new)
          heapq.heappush(r, _r)
          heapq.heappush(r, m)
          m, L, R = _l, L+new, R+m
        elif new <= m:
          heapq.heappush(l, -_l)
          heapq.heappush(r, _r)
          heapq.heappush(r, m)
          m, L, R = new, L+new, R+m
        else:
          heapq.heappush(l, -_l)
          heapq.heappush(r, _r)
          heapq.heappush(r, new)
          L, R = L+m, R+new
      else:
        if new <= m:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -new)
          heapq.heappush(r, _r)
          L += new - m
        elif new <= _r:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -m)
          heapq.heappush(r, _r)
          m = new
        else:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -m)
          heapq.heappush(r, new)
          m, R = _r, R+new-_r
    n += 1
  else: # 求値クエリ
    print(m, R-L+b)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
import numpy as np
_,a,b=map(int,input().split())
A=np.array([a])
B=b
for i in range(Q-1):
  query=list(map(int,input().split()))
  if query[0]==1:
    A=np.insert(A, np.searchsorted(A,query[1]), query[1])
    B+=query[2]
  else:
    x=A[(len(A)-1)//2]
    ans=np.sum(np.abs(A-x))+B
    print(x,ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    Q = int(input())
    n,a,b = map(int,input().split())
    ms = -a
    ps = 0
    cs = b
    ml = [-a]
    pl = []
    heapq.heapify(ml)
    heapq.heapify(pl)
    for _ in range(Q-1):
        X = list(map(int,input().split()))
        if X[0] == 1:
            n,a,b = X
            cs += b
            if len(ml) != len(pl):
                s = heapq.heappop(ml)*(-1)
                ms += s
                if s <= a:
                    heapq.heappush(pl,a)
                    ps += a
                    heapq.heappush(ml,-s)
                    ms -= s
                else:
                    heapq.heappush(pl,s)
                    ps += s
                    heapq.heappush(ml,-a)
                    ms -= a
            else:
                s = heapq.heappop(pl)
                ps -= s
                if s <= a:
                    heapq.heappush(pl,a)
                    ps += a
                    heapq.heappush(ml,-s)
                    ms -= s
                else:
                    heapq.heappush(pl,s)
                    ps += s
                    heapq.heappush(ml,-a)
                    ms -= a
        else:
            pos = min(ml)*(-1)
            left = pos*(len(ml))+ms
            right = ps-pos*(len(pl))
            print(pos,left+right+cs)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

q = int(input())
inf = 10000000000
left = [inf]
right = [inf]
minval = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, a, b = query
        if a < -left[0]:
            v = -heapq.heappop(left)
            heapq.heappush(right, v)
            heapq.heappush(left, -a)
            heapq.heappush(left, -a)
            minval += abs(v - a) + b
        elif a > right[0]:
            v = heapq.heappop(right)
            heapq.heappush(left, -v)
            heapq.heappush(right, a)
            heapq.heappush(right, a)
            minval += abs(v - a) + b
        else:
            heapq.heappush(left, -a)
            heapq.heappush(right, a)
            minval += b
    else:
        print(-left[0], minval)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    q=int(input())
    res = 0

    x=list(map(int,input().split()))
    a=x[1]
    res += x[2]
    asmall = [a*-1]
    alarge = [a]
    heapq.heapify(asmall)
    heapq.heapify(alarge)

    r1 = a
    r2 = a

    for _ in range(q-1):
        x=list(map(int,input().split()))
        if x[0] ==1:
            a = x[1]
            res += x[2]
            if r1 <= a and a <= r2: pass
            else: res += min(abs(a-r1),abs(a-r2))
            mid1 = asmall[0] * -1
            if mid1 > a:
                heapq.heappush(alarge,heapq.heappop(asmall) * -1)
                heapq.heappush(asmall,-a)
                heapq.heappush(asmall,-a)
            else:
                mid2 = alarge[0]
                if mid2 >= a:
                    heapq.heappush(asmall,-a)
                    heapq.heappush(alarge,a)
                else:
                    heapq.heappush(asmall,heapq.heappop(alarge) * -1)
                    heapq.heappush(alarge,a)
                    heapq.heappush(alarge,a)
            r1 = asmall[0] * -1
            r2 = alarge[0]
        if x[0] == 2:
            print(str(r1)+" "+str(res))

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

q=int(input())
res = 0

x=list(map(int,input().split()))
a=x[1]
res += x[2]
asmall = [a*-1]
alarge = [a]
heapq.heapify(asmall)
heapq.heapify(alarge)

r1 = a
r2 = a

for _ in range(q-1):
    x=list(map(int,input().split()))
    if x[0] ==1:
        a = x[1]
        res += x[2]
        if r1 <= a and a <= r2: pass
        else: res += min(abs(a-r1),abs(a-r2))
        mid1 = asmall[0] * -1
        if mid1 > a:
            heapq.heappush(alarge,heapq.heappop(asmall) * -1)
            heapq.heappush(asmall,-a)
            heapq.heappush(asmall,-a)
        else:
            mid2 = alarge[0]
            if mid2 >= a:
                heapq.heappush(asmall,-a)
                heapq.heappush(alarge,a)
            else:
                heapq.heappush(asmall,heapq.heappop(alarge) * -1)
                heapq.heappush(alarge,a)
                heapq.heappush(alarge,a)
        r1 = asmall[0] * -1
        r2 = alarge[0]
    if x[0] == 2:
        print(str(r1)+" "+str(res))

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
a=[]
b = 0

def query2(a,b,x):
    ret = b
    for sa in a:
        ret += abs(x-sa)
    return ret


for _ in range(q):
    x=list(map(int,input().split()))
    if x[0] ==1:
        a.append(x[1])
        b += x[2]
    elif x[0] == 2:
        a.sort()
        r1 = a[(len(a)-1)//2]
        r2 = query2(a,b,r1)
        print(str(r1)+" "+str(r2))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = list(map(int, input().split()))
a = [s[1]]
ans = s[2]
p = 0

for i in range(n-1):
    q = input()
    if q[0]=='1':
        c,d = map(int,q[2:].split())
        if len(a)%2==1:
            ans+=abs(a[p]-c)+d
            bisect.insort(a,c)
        else:
            p+=1
            bisect.insort(a,c)
            ans+=abs(a[p]-c)+d
    else:
        print(a[p], ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = list(map(int, input().split()))
a = [s[1]]
ans = s[2]
p = 0

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        b = bisect.bisect_left(a, q[1])
        if len(a)%2==1:
            ans+=abs(a[p]-q[1])
            a=a[:b]+[q[1]]+a[b:]
        else:
            p+=1
            a=a[:b]+[q[1]]+a[b:]
            ans+=abs(a[p]-q[1])
    if q[0]==2:
        print(a[p], ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [list(map(int, input().split()))for i in range(n)]

l = [[s[0][1]]]

for i in range(1,n):
    if s[i][0]==1:
        l.append(l[-1]+[s[i][1]])
        l[-1].sort()
    else:
        l.append(l[-1])

ans = s[0][2]
p = 0

for i in range(1,n):
    q = s[i]
    if q[0]==1:
        ans += q[2]
        if len(l[i-1])%2==1:
            ans+=abs(l[i-1][p]-q[1])
        else:
            p+=1
            ans+=abs(l[i][p]-q[1])
    if q[0]==2:
        print(l[i][p], ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = list(map(int, input().split()))
a = [s[1]]
ans = s[2]
p = 0

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if len(a)%2==1:
            ans+=abs(a[p]-q[1])
            bisect.insort(a,q[1])
        else:
            p+=1
            bisect.insort(a,q[1])
            ans+=abs(a[p]-q[1])
    if q[0]==2:
        print(a[p], ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect,insort
import itertools
q=int(input())
query=[list(map(int,input().split())) for i in range(q)]
inf=float("inf")
a_sum=0
b_sum=0
A=[]
count=0
for u in query:
    if u[0]==2:
        if count%2==1:
            print(A[num],a_sum+b_sum-A[num])
        else:
            print(A[num-1],a_sum+b_sum)
    else:
        count+=1
        a,b=u[1],u[2]
        b_sum+=b
        c=bisect(A,a)
        num=count//2
        if c>=num:
            if count%2==0:
                a_sum+=-2*A[num-1]+a
            else:
                a_sum+=a
            A=list(itertools.chain(A[:c],[a],A[c:]))
        else:
            if count%2==0:
                a_sum+=-a
            else:
                a_sum+=-a+2*A[num-1]
            A=list(itertools.chain(A[:c],[a],A[c:]))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect,insort
import itertools
q=int(input())
query=[list(map(int,input().split())) for i in range(q)]
inf=float("inf")
a_sum=0
b_sum=0
A=[]
count=0
for u in query:
    if u[0]==2:
        if count%2==1:
            print(A[num],a_sum+b_sum-A[num])
        else:
            print(A[num-1],a_sum+b_sum)
    else:
        count+=1
        a,b=u[1],u[2]
        b_sum+=b
        c=bisect(A,a)
        num=count//2
        if c>=num:
            if count%2==0:
                a_sum+=-2*A[num-1]+a
            else:
                a_sum+=a
            insort(A,a)
        else:
            if count%2==0:
                a_sum+=-a
            else:
                a_sum+=-a+2*A[num-1]
            insort(A,a)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect,insort_left
import itertools
q=int(input())
query=[list(map(int,input().split())) for i in range(q)]
inf=float("inf")
a_sum=0
b_sum=0
A=[]
count=0
for u in query:
    if u[0]==2:
        if count%2==1:
            num=count//2
            print(A[num][0],a_sum+b_sum-A[num][0])
        else:
            num=count//2
            print(A[num-1][0],a_sum+b_sum)
    else:
        count+=1
        a,b=u[1],u[2]
        b_sum+=b
        c=bisect(A,[a,-inf])
        num=count//2
        if c>=num:
            A=list(itertools.chain(A[:c],[[a,a]],A[c:]))
            a_sum+=a
        else:
            A=list(itertools.chain(A[:c],[[a,-a]],A[c:]))
            a_sum+=-a
        if num==0:
            continue
        if A[num-1][1]==A[num-1][0]:
            a_sum+=-2*A[num-1][0]
            A[num-1][1]=-A[num-1][0]
        if A[num][1]!=A[num][0]:
            a_sum+=2*A[num][0]
            A[num][1]=A[num][0]

Submission status: Time Limit Exceeded

Solution code:
import bisect
q=int(input())
A=[]
b=0
c=0
for i in range(q):
  Q=list(map(int,input().split()))
  if Q[0]==1:
    A.insert(bisect.bisect_left(A, Q[1], lo=0, hi=len(A)), Q[1])
    b=b+Q[2]
    c=c+1
  else:
    if c%2==1:
      a=A[(c-1)//2]
      print(a,end=" ")
      d=0
      for i in range(c):
        d=d+abs(A[i]-a)
      print(d+b)
    else:
      a=A[(c-2)//2]
      print(a,end=" ")
      d=0
      for i in range(c):
        d=d+abs(A[i]-a)
      print(d+b)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(x, key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.n_bit_length = n.bit_length()
        self.bit = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << (self.n_bit_length - 1)
        while k:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


q = int(input())
query = []
coord = set()
for _ in range(q):
    s = input()
    if s[0] == '1':
        # update query
        _, a, b = map(int, s.split())
        coord.add(a)
        query.append((1, a, b))
    else:
        # evaluation query
        query.append((2, ))

zipped, unzipped = compress_coordinate(list(coord))
a_sum = b_sum = 0
bit = BIT1(len(coord))
for qi in query:
    if qi[0] == 1:
        a = qi[1]
        b = qi[2]

        n = bit.sum(len(coord))
        if n > 0:
            a_min_l = unzipped[bit.bisect_left(n // 2)]
            a_min_r = unzipped[bit.bisect_left(n // 2 + 1)]
            if a < a_min_l:
                a_sum += a_min_l - a
            elif a > a_min_r:
                a_sum += a - a_min_r

        b_sum += b
        bit.add(zipped[a], 2)
    else:
        n = bit.sum(len(coord))
        idx1 = bit.bisect_left(n // 2)
        print(unzipped[idx1], b_sum + a_sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(x, key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.n_bit_length = n.bit_length()
        self.bit = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << (self.n_bit_length - 1)
        while k:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


q = int(input())
query = []
coord = set()
for _ in range(q):
    s = input()
    if s[0] == '1':
        # update query
        _, a, b = map(int, s.split())
        coord.add(a)
        query.append((1, a, b))
    else:
        # evaluation query
        query.append((2, ))

zipped, unzipped = compress_coordinate(list(coord))
a_sum = b_sum = 0
bit = BIT1(len(coord))
for i in range(q):
    if query[i][0] == 1:
        a = query[i][1]
        b = query[i][2]

        if i > 0:
            n = bit.sum(len(coord))
            a_min_l = unzipped[bit.bisect_left(n // 2)]
            a_min_r = unzipped[bit.bisect_left(n // 2 + 1)]
            if a < a_min_l:
                a_sum += a_min_l - a
            elif a > a_min_r:
                a_sum += a - a_min_r

        b_sum += b
        bit.add(zipped[a], 2)
    else:
        n = bit.sum(len(coord))
        idx1 = bit.bisect_left(n // 2)
        print(unzipped[idx1], b_sum + a_sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(x, key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.n_bit_length = n.bit_length()
        self.bit = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << (self.n_bit_length - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


q = int(input())
query = []
coord = set()
for _ in range(q):
    s = input()
    if s[0] == '1':
        # update query
        _, a, b = map(int, s.split())
        coord.add(a)
        query.append((1, a, b))
    else:
        # evaluation query
        query.append((2, ))

zipped, unzipped = compress_coordinate(list(coord))
a_sum = b_sum = 0
bit = BIT1(len(coord))
for i in range(q):
    if query[i][0] == 1:
        a = query[i][1]
        b = query[i][2]

        if i > 0:
            n = bit.sum(len(coord))
            a_min_l = unzipped[bit.bisect_left(n // 2)]
            a_min_r = unzipped[bit.bisect_left(n // 2 + 1)]
            if a < a_min_l:
                a_sum += a_min_l - a
            elif a > a_min_r:
                a_sum += a - a_min_r

        b_sum += b
        bit.add(zipped[a], 2)
    else:
        n = bit.sum(len(coord))
        idx1 = bit.bisect_left(n // 2)
        print(unzipped[idx1], b_sum + a_sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(x, key=None, reverse=reverse)):
        zipped[xi] = i + 1
        unzipped[i + 1] = xi
    return zipped, unzipped


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


q = int(input())
query = []
coord = set()
for _ in range(q):
    s = input()
    if s[0] == '1':
        # update query
        _, a, b = map(int, s.split())
        coord.add(a)
        query.append((1, a, b))
    else:
        # evaluation query
        query.append((2, ))

zipped, unzipped = compress_coordinate(list(coord))
a_sum = b_sum = 0
bit = BIT1(len(coord))
for i in range(q):
    if query[i][0] == 1:
        a = query[i][1]
        b = query[i][2]

        if i > 0:
            n = bit.sum(len(coord))
            idx1 = bit.bisect_left(n // 2)
            idx2 = bit.bisect_left(n // 2 + 1)
            if a < unzipped[idx1]:
                a_sum += unzipped[idx1] - a
            elif a > unzipped[idx2]:
                a_sum += a - unzipped[idx2]

        b_sum += b
        bit.add(zipped[a], 2)
    else:
        n = bit.sum(len(coord))
        idx1 = bit.bisect_left(n // 2)
        print(unzipped[idx1], b_sum + a_sum)

Submission status: Time Limit Exceeded

Solution code:

# ABC140E
import sys
input = sys.stdin.readline
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
q=int(input())
xs = []
ys = []
qs = dict()
c = 0
for _ in range(q):
    xy = list(map(int,input().split()))
    if len(xy) == 1:
        if c not in qs:
            qs[c] = 0
        qs[c] += 1
    else:
        c += 1
        xs.append(xy[1])
        ys.append(xy[2])

N=len(xs)
sxs=sorted(xs)
zxs = [0]*N
for i, x in enumerate(sorted(range(N), key=lambda x : xs[x])):
    zxs[x] = i

seg_sum_tree = SegTree([0]*N, N, 0, lambda x, y: x+y)
seg_count_tree = SegTree([0]*N, N, 0, lambda x, y: x+y)

sy = 0
for i in range(c+1):
    if i in qs:
        x1i=bsearch(i//2 + (-1 if i % 2 == 0 else 0) ,0 ,N-1 ,lambda x : seg_count_tree.query(0, x))
#        print(x1i, i//2, seg_count_tree.query(0, 2))
        if i % 2:
        #print(sy, seg_sum_tree.query(0, x1i))
            r = sy - seg_sum_tree.query(0, x1i) + \
                   seg_sum_tree.query(x1i+1, N)
        else:
            r = sy - seg_sum_tree.query(0, x1i+1) + \
                   seg_sum_tree.query(x1i+1, N)
        for _ in range(qs[i]):
            print(sxs[x1i], r)
    if i == c:
        break
    x, y = xs[i], ys[i]
    xi = zxs[i]
    sy += y
    seg_sum_tree.update(xi, x)
    seg_count_tree.update(xi, 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import bisect
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
1 4 2
2
1 1 -8
2"""
        output = """4 2
1 -3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2"""
        output = """-1000000000 3000000000"""
        self.assertIO(input, output)
def fx(a,b):
    x=len(a)
    x=int((x-1)/2) if x%2==1 else int(x/2)-1
    ax=a[x]
    ans=sum([abs(i-ax) for i in a])+b
    print(ax,ans)


def resolve():
    Qn=int(input())
    a=[]
    (_,aa,b)=(int(i) for i in input().split())
    a.append(aa)

    for j in range(Qn-1):

        q=input()
        if q=='2':
            fx(a,b)
        else:
            (_,aa,bb)=(int(i) for i in q.split())
            b+=bb
            bisect.insort(a,aa)





if __name__ == "__main__":
    resolve()