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 math

class Avltree:
    """
    AVL木

    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"

    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None

    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans

    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans

    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key

    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key

    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr

    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl

    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr

    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl

    def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else:
            p.right = v

    def insert(self, key):  # rootでのみ呼ばれる挿入
        if self.key is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite

    def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break

    def to_s(self):
        return self.key

    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key

    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key


b_sum = 0
left_sum = 0
right_sum = 0
piv = None
Q = int(input())
cnt = 0
bt = Avltree()
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        a, b = q[1], q[2]
        b_sum += b
        bt.insert(a)
        if piv is None:
            piv = a
        elif cnt % 2 == 0:
            if a <= piv:
                left_sum += (piv - a)
            else:
                np = bt.search_higher(piv, math.inf)
                left_sum += (np - piv) * (cnt // 2)
                right_sum -= (np - piv) * (cnt // 2)
                right_sum += a - np
                piv = np
        elif cnt % 2 == 1:
            if a < piv:
                np = bt.search_lower(piv, -1*math.inf)
                left_sum -= (piv - np) * (cnt // 2)
                right_sum += (piv - np) * (cnt // 2 + 1)
                left_sum += (np-a)
                piv = np
            else:
                right_sum += (a - piv)
        cnt += 1

    elif q[0] == 2:
        ans = b_sum + left_sum + right_sum
        print(piv, ans)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
query=[input() for _ in range(q)]
from bisect import bisect_left
ary=[-float('inf')]
for qq in query:
  if qq[0]=='1':
    _,a,_=map(int,qq.split())
    ary.append(a)
ary.sort()
ary.append(float('inf'))

class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  # 区間[l,r)へのクエリ
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)

ml,mr=0,len(ary)+1
mv=0
st=SegmentTree(len(ary))
for qq in query:
  if qq[0]=='2':
    print(ary[ml],mv)
  else:
    _,a,b=map(int,qq.split())
    a=bisect_left(ary,a)
    st.add(0,-1)
    st.add(a,2)
    if ml<=a<mr:
      mv+=b
      ml,mr=a,a+1
    else:
      l,r=0,len(ary)+1
      # はじめて0以上になる場所を二分探索→ここがml
      while r-l>1:
        x=(r+l)//2
        if st.query(0,x)>=0:
          l,r=l,x
        else:
          l,r=x,r
      # はじめて1以上になる場所を二分探索→ここがmr
      mv+=b
      mv+=min(abs(ary[l]-ary[ml]),abs(ary[l]-ary[mr]))+abs(ary[l]-ary[a])
      ml=l
      l,r=0,len(ary)+1
      while r-l>1:
        x=(r+l)//2
        if st.query(0,x)>0:
          l,r=l,x
        else:
          l,r=x,r
      mr=l

Submission status: Time Limit Exceeded

Solution code:
import bisect
Q = int(input())

A = []
now_a = 0
now_a_score = 0
min_score = 0
nn = 0
for i in range(Q):
  Q1 = list(map(int, input().split()))
  if len(Q1) == 3:#更新
    nn += 1
    a, b = Q1[1], Q1[2]
    A.append(a)
    A = sorted(A)
    now_a = A[int((nn - 1) / 2)]
    now_a_score = 0
    for j in range(nn):
      now_a_score += abs(A[j] - now_a) 
    #print(now_a, a, now_a_score)  
    min_score += b
  else:#求値
    print(now_a, min_score + now_a_score)

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        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:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < 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

def main():
    q = int(input())
    ans = []
    query = [list(map(int, input().split())) for _ in range(q)]
    a_arr = []
    for arr in query:
        if arr[0] == 1:
            a_arr.append(arr[1])
    a_arr.sort()
    dic = {}
    rev_dic = {}
    p = 0
    for v in a_arr:
        if not v in dic:
            dic[v] = p
            rev_dic[p] = v
            p += 1
    seg_arr = [0]*p
    seg = SegTree(0, p, seg_arr)
    b_sum = 0
    cnt = 0
    add = 0
    f = False
    range_L, range_R = -1, -1
    for arr in query:
        if arr[0] == 1:
            x = dic[arr[1]]
            b_sum += arr[2]
            seg_arr[x] += 2
            seg.update(x, seg_arr[x])
            cnt += 1
            if f:
                if range_L <= x <= range_R:
                    add += 0
                elif x < range_L:
                    add += rev_dic[range_L] - arr[1]
                else:
                    add += arr[1] - rev_dic[range_R]
        L, R = -1, p-1
        while L+1 < R:
            P = (L+R+1)//2
            if seg.query(0, P+1)-cnt >= 0:
                R = P
            else:
                L = P
        range_L = R
        L, R = 0, p
        while L+1 < R:
            P = (L+R)//2
            if seg.query(P, p)-cnt >= 0:
                L = P
            else:
                R = P
        range_R = L
        f = True
        if arr[0] == 2:
            ans.append([rev_dic[range_L], b_sum + add])
    for a, b in ans:
        print(a, b)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
a = []
ai = 0
bs = 0
for i in range(q):
    ipt = list(map(int,input().split()))
    if ipt[0] == 1:
        a.append(ipt[1])
        bs += ipt[2]
        ai += 1
    else:
        a.sort()
        an = a[(ai-1)//2]
        bn = bs
        for j in a:
            bn += abs(j-an)
        print(an,bn)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from bisect import insort

class BIT():
 
    def __init__(self, n):
        '''
        n = 要素数
        添字は i = 0 ~ n-1 となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)
 
    def add(self, i, x):
        '''i番目の要素にxを加算する'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
 
    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
 
    def get(self, i, j):
        '''[i, j)の和を求める'''
        return self._sum(j) - self._sum(i)
  
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return memo, len(list2)

q = int(readline())
info = [list(map(int, input().split())) for i in range(q)]
 
#座圧する
li1 = []
for i in range(q):
    if info[i][0] == 1:
        li1.append(info[i][1])
        
memo, len_memo = compress(li1)
#print(memo,len_memo)

#値を管理するBIT
bit = BIT(len_memo)
#要素数を管理するBITに
bit1 = BIT(len_memo)

ch = []
cnt = 0
s = 0
for i in range(q):
  que = info[i]
  if que[0] == 1:
    a,b,c = que
    insort(ch,b)
    cnt += 1
    s += c
    bit.add(memo[b],b)
    bit1.add(memo[b], 1)
  else:
    if cnt%2 == 1:
      d = ch[cnt//2]
    else:
      d = ch[cnt//2-1]
    sum1 = bit.get(0, memo[d])
    num1 = bit1.get(0, memo[d])
    sum2 = bit.get(memo[d], len_memo)
    num2 = bit1.get(memo[d], len_memo)
    print(d, abs(num1*d- sum1) + abs(num2*d - sum2) + s)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from bisect import insort
q = int(readline())
ch = []
cs = 0
cnt = 0
s = 0
for i in range(q):
  que = list(map(int,readline().split()))
  if que[0] == 1:
    a,b,c = que
    insort(ch,b)
    cnt += 1
    cs += b
    s += c
  else:
    if cnt%2 == 1:
      if cnt == 1:
        print(ch[0],s)
      else:
        d = ch[cnt//2]
        print(d,cs-2*sum(ch[:cnt//2])-d+s)
    else:
      if cnt == 2:
        print(ch[0],ch[1]-ch[0]+s)
      else:
        print(ch[cnt//2-1],cs-2*sum(ch[:cnt//2])+s)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(Q):
    sb = 0

    l = []
    r = []
    spa = 0
    npa = 0
    sna = 0
    nna = 0

    for q in Q:
        if q[0] == 1:
            _, a, b = q
            if a > 0:
                spa += a
                npa += 1
            else:
                sna += a
                nna += 1
            heapq.heappush(l, -a)

            if len(l) > len(r) + 1:
                heapq.heappush(r, -heapq.heappop(l))

            while l and r and -l[0] > r[0]:
                heapq.heappush(r, -heapq.heappop(l))
                heapq.heappush(l, -heapq.heappop(r))

            sb += b
        else:
            x = -l[0]
            # error_print(l, r, x, sb)
            print(x, abs(-sum(l) - len(l)*x) + abs(sum(r) - len(r)*x) + sb)

def main():
    N = read_int()
    Q = [read_int_n() for _ in range(N)]
    slv(Q)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())

alist=[]
b=0
for _ in range(Q):
  query=list(map(int,input().split()))
  if len(query)==3:
    dummy,ai,bi=query
    alist.append(ai)
    alist.sort()
    b+=bi
  else:
    minarg=alist[(len(alist)-1)//2]
    minvalue=b
    for i in range(len(alist)):
      minvalue+=abs(alist[i]-minarg)
    print(minarg,minvalue)

Submission status: Time Limit Exceeded

Solution code:
import heapq

q = int(input())

nchange = 0
ming, maxg = [], []
heapq.heapify(ming)
heapq.heapify(maxg)
a = 0
b = 0
for i in range(q):
    qi = input()
    if qi[0] == '1':
        _, ai, bi = map(int, qi.split())
        b += bi
        nchange += 1
        if nchange % 2 == 1:
            if nchange == 1:
                x = ai
                continue
            Smax = -heapq.heappop(ming)
            Dmin = heapq.heappop(maxg)
            if Smax <= ai and ai <= Dmin:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, Dmin)
                x = ai
            elif ai < Smax:
                heapq.heappush(ming, -ai)
                heapq.heappush(maxg, Dmin)
                x = Smax
                a += Smax - ai
            else:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, ai)
                x = Dmin
                a += ai - Dmin
        else:
            heapq.heappush(ming, -min(x, ai))
            heapq.heappush(maxg, max(x, ai))
            a += abs(x - ai)
            x = -heapq.heappop(ming)
            heapq.heappush(ming, -x)
    else:
        print(x, a+b)

Submission status: Time Limit Exceeded

Solution code:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    q = int(input())
    array = []
    con = 0
    cur_x = 0
    cur_val = 0
    length = 0

    import bisect

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            new = val[1]
            con += val[2]
            bisect.insort_left(array, new)
            length += 1
            prev_x = cur_x
            cur_x = array[(length - 1) // 2]
            if length % 2 == 1:
                cur_val += abs(new - cur_x)
            else:
                cur_val += abs(new - cur_x) + abs(prev_x - cur_x)

        if val[0] == 2:
            print(cur_x, cur_val + con)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

q = int(input())
l = []
r = []
ans = 0

for i in range(q):
    a = list(map(int,input().split()))
    if a[0] == 1:
        ans += a[2]
        if l == []:
            heapq.heappush(r,a[1])
            heapq.heappush(l,-a[1])
        else: 
            ll = -heapq.heappop(l)
            rr = heapq.heappop(r)
            if ll <= a[1] <= rr:
                heapq.heappush(r,rr)
                heapq.heappush(l,-ll) 
                heapq.heappush(r,a[1])
                heapq.heappush(l,-a[1]) 

            elif ll > a[1]:
                ans += ll-a[1]
                heapq.heappush(r,rr)
                heapq.heappush(r,ll) 
                heapq.heappush(l,-a[1])
                heapq.heappush(l,-a[1]) 
            else:
                ans += a[1] -rr
                heapq.heappush(l,-rr)
                heapq.heappush(l,-ll) 
                heapq.heappush(r,a[1])
                heapq.heappush(r,a[1]) 
        
    else:
        a = heapq.heappop(l)
        print(-a,ans)
        heapq.heappush(l,a)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    q = int(input())
    l = []
    b = 0
    count = 0
    for i in range(q):
        a = list(map(int,input().split()))
        if a[0] == 1:
            l.append(a[1])
            count += 1
            b += a[2]
        else:
            l.sort()
            if count %2 == 0:
                ans = sum(l[(count-1)//2+1:])-sum(l[:(count-1)//2+1])
                print(l[(count-1)//2],ans+b)
            else:
                ans = sum(l[(count-1)//2+1:])-sum(l[:(count-1)//2])
                print(l[(count-1)//2],ans+b)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    q = int(input())
    l = []
    b = 0
    count = 0
    for i in range(q):
        a = list(map(int,input().split()))
        if a[0] == 1:
            l.append(a[1])
            count += 1
            b += a[2]
        else:
            l.sort()
            x = l[(count-1)//2]
            
            ans = 0
            for i in l:
                ans += abs(x-i)
            print(x,ans+b)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
l = []
b = 0
count = 0
for i in range(q):
    a = list(map(int,input().split()))
    if a[0] == 1:
        l.append(a[1])
        count += 1
        b += a[2]
    else:
        l.sort()
        x = l[(count-1)//2]
        
        ans = 0
        for i in l:
            ans += abs(x-i)
        print(x,ans+b)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
query = []
mid = []
for _ in range(Q):
    a = list(map(int, input().split()))
    query.append(a)


for i in range(len(query)):
    if query[i][0] == 1:
        mid.append(query[i][1:])

    else:
        ans = 0
        mid.sort(key=lambda x: x[0])
        minx = int((len(mid)+1)/2)
        for j in mid:
            ans += abs(mid[minx-1][0]-j[0])+j[1]
        print(mid[minx-1][0],ans)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
q=[]
a=[]
b=0
n=0
def dist(A,x,n):
  ret=0
  for i in range(n):
    ret+=abs(A[i]-x)
  return ret
for i in range(Q):
  q.append(list(map(int,input().split())))
  if q[i][0]==2:
    if len(a)%2==0:
      x=a[len(a)//2-1]
      fx=dist(a,x,n)+b
      print(x,fx)
    else:
      x=a[len(a)//2]
      fx=dist(a,x,n)+b
      print(x,fx)
  else:
    n+=1
    a.append(q[i][1])
    b+=q[i][2]
    a.sort()

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
q=[]
a=[]
b=0
def dist(A,x):
  ret=0
  for i in range(len(A)):
    ret+=abs(A[i]-x)
  return ret
for i in range(Q):
  q.append(list(map(int,input().split())))
  if q[i][0]==2:
    if len(a)%2==0:
      x=a[len(a)//2-1]
      fx=dist(a,x)+b
      print(x,fx)
    else:
      x=a[len(a)//2]
      fx=dist(a,x)+b
      print(x,fx)
  else:
    a.append(q[i][1])
    b+=q[i][2]
    a.sort()

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('l',
                         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))