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: Runtime Error

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

from heapq import heappush, heappop

Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

t = 0
u = 0
eo = 0
max_sum, min_sum = 0, 0
buf = 0

h_max = []
h_min = []
h_tmp = []

for i in range(Q):
    if Query[i][0] == 2:
        if eo % 2 == 1:
            if eo > 1:
                b = -heappop(h_min)
                c = heappop(h_max)
                d = heappop(h_tmp)
                b, c, d = sorted([b, c, d])
                heappush(h_min, -b)
                heappush(h_max, d)
                heappush(h_tmp, c)
                print(c, max_sum - min_sum + t)
            else:
                d = heappop(h_tmp)
                print(d,t)
                heappush(h_tmp, d)
        else:
            b = -heappop(h_min)
            print(b, max_sum - min_sum + t)
            heappush(h_min, -b)
    else:
        heappush(h_tmp, Query[i][1])
        t += Query[i][2]
        if eo % 2 == 1:
            if eo == 1:
                b = heappop(h_tmp)
                heappush(h_min, -b)
                min_sum += b
                b = heappop(h_tmp)
                heappush(h_max, b)
                max_sum += b

            elif eo == 2:
                b = -heappop(h_min)
                min_sum -= b
                heappush(h_tmp, b)
                b = heappop(h_max)
                min_sum -= b
                heappush(h_tmp, b)

                b = heappop(h_tmp)
                heappush(h_min, -b)
                min_sum += b
                b = heappop(h_tmp)
                heappush(h_min, -b)
                min_sum += b

                b = heappop(h_tmp)
                heappush(h_max, b)
                max_sum += b
                b = heappop(h_tmp)
                heappush(h_max, b)
                max_sum += b

            elif eo >= 2:
                b = -heappop(h_min)
                min_sum -= b
                heappush(h_tmp, b)
                b = -heappop(h_min)
                min_sum -= b
                heappush(h_tmp, b)
                b = heappop(h_max)
                min_sum -= b
                heappush(h_tmp, b)
                b = heappop(h_max)
                min_sum -= b
                heappush(h_tmp, b)

                b = heappop(h_tmp)
                heappush(h_min, -b)
                min_sum += b
                b = heappop(h_tmp)
                heappush(h_min, -b)
                min_sum += b
                b = heappop(h_tmp)
                heappush(h_min, -b)
                min_sum += b

                b = heappop(h_tmp)
                heappush(h_max, b)
                max_sum += b
                b = heappop(h_tmp)
                heappush(h_max, b)
                max_sum += b
                b = heappop(h_tmp)
                heappush(h_max, b)
                max_sum += b

        eo += 1

Submission status: Runtime Error

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(roght)
            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(right[0], minval)

Submission status: Runtime Error

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
            itertools.chain(A[:c],[a],A[c:])
        else:
            if count%2==0:
                a_sum+=-a
            else:
                a_sum+=-a+2*A[num-1]
            itertools.chain(A[:c],[a],A[c:])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size

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

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def total(self):
        return self.bit[self.size - 1]

    def interval_sum(self, i, j): # i <= x <= j の区間
        return self.sum(j) - self.sum(i - 1)

    def search(self, k):
        if k > self.bit[self.size - 1]:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index


q = I()
query = []
A = []
for _ in range(q):
    l = LI()
    if l[0] == 1:
        A += [l[1]]
    query += [l]



ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i


bit1 = BIT(len(A))
bit2 = BIT(len(A))
n = 0
B = 0
for l in query:
    if l[0] == 1:
        B += l[2]
        bit1.add(co_to_ind[l[1]], 1)
        bit2.add(co_to_ind[l[1]], l[1])
        n += 1
    else:
        min_ind = bit1.search(n // 2 + bool(n % 2))
        min_val = bit2.total() - bit2.sum(min_ind) - (bit1.total() - bit1.sum(min_ind)) * ind_to_co[min_ind] \
            + bit1.sum(min_ind - 1) * ind_to_co[min_ind] - bit2.sum(min_ind - 1) + B
        print(ind_to_co[min_ind], min_val)

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq
Q = int(input())
Qlist = [list(map(int,input().split())) for i in range(Q)]
#print(Qlist)
coef_list = []
intercept = [0]
left_list = []
cent_list = []
right_list = []
left_sum = [0]
right_sum = [0]

median = [0]
count = [0,0]

def update_func(query):
    source = query[1]
    coef_list.append(query[1])
    intercept[0] += query[2]

    if len(coef_list) == 1:
        cent_list.append(source)
        median[0] = cent_list[0]
        return
    if cent_list == []:
        if median[0] > source:
            heapq.heappush(left_list, -source)
            left_sum[0] += source #
            tmp = -heapq.heappop(left_list)
            left_sum[0] -= tmp #
            cent_list.append(tmp)
        elif right_list[0] > source:
            cent_list.append(source)
        else:
            heapq.heappush(right_list, source)
            tmp = heapq.heappop(right_list)
            right_sum[0] += source - tmp
            cent_list.append(tmp)
        median[0] = cent_list[0]
    else:
        if cent_list[0] < source:
            heapq.heappush(left_list, -cent_list[0])
            count[0] += 1
            left_sum[0] += cent_list[0]
            median[0] = cent_list[0]
            heapq.heappush(right_list, source)
            count[1] += 1
            right_sum[0] += source
            cent_list.remove(cent_list[0])
        else:
            heapq.heappush(left_list, -source)
            left_sum[0] += source - tmp
            count[0] += 1
            median[0] = source
            heapq.heappush(right_list, cent_list[0])
            count[1] += 1
            right_sum[0] += cent_list[0]
            cent_list.remove(cent_list[0])
    return
def solve_func():
    cent = 0
    if cent_list != []:
        cent = cent_list[0]
    minval = np.abs(left_sum[0]-count[0]*median[0]) + np.abs(right_sum[0]-count[1]*median[0]) + cent - len(cent_list)*median[0]
    minval += intercept[0]
    print(str(median[0]) + " " + str(minval))

for query in Qlist:
    if query[0] == 1:
        update_func(query)
    else:
        solve_func()

Submission status: Runtime Error

Solution code:
from heapq import heappop
from heapq import heappush
q=int(input())
L,R=[],[]
b_sum=0
l_sum,r_sum=0,0
count=0
mid=0
for _ in range(q):
  
  Q=list(map(int,input().split()))
  if Q[0]==1:
    a,b=Q[1],Q[2]
    count+=1
    b_sum+=b
    if count==1:
      mid=a
    elif count%2==0:
      if a<=mid:
        heappush(L,-a)
        l_sum+=a
        heappush(R,mid)
        r_sum+=mid
      else:
        heappush(L,-mid)
        l_sum+=mid
        heappush(R,a)
        r_sum+=a
    else:
      l,r=-heappop(L),heappop(R)
      if a<l:
        heappush(L,-a)
        l_sum+=a-l
        mid=l
        heappush(R,r)
      elif r<a:
        heappush(L,-l)
        mid=r
        heappush(R,a)
        r_sum+=a-r
      else:
        heappush(L,-l)
        mid=a
        heappush(R,r)

  else:
    if count%2==1:
      print(mid,r_sum-l_sum+b_sum)
    else:
      print(-heappop(L),r_sum-l_sum+b_sum)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappushpop

Q = int(input())

b = 0
la = []
sl = 0
ra = []
sr = 0

cnt = 0
for _ in range(Q):
    q = map(int, input().split())
    # print(la, ra)
    if q[0] == 2:
        # 求値
        x = -la[0]
        cl = (cnt + 1) // 2
        cr = cnt - cl
        print(x, (cl * x - sl) + (sr - cr * x) + b)
    else:
        # 更新
        b += q[2]
        cnt += 1
        if cnt % 2 == 1:
            sr += q[1]
            x = heappushpop(ra, q[1])
            sr -= x
            sl += x
            heappush(la, -x)
        else:
            sl += q[1]
            x = heappushpop(la, -q[1])
            x *= -1
            sl -= x
            sr += x
            heappush(ra, x)

Submission status: Runtime Error

Solution code:
Q=int(input())
A=[]
B=0
j=0
Que0=list(map(int,input().split(" ")))
A=[Que0[1]]
B=Que0[2]
min=0
for i in range (1,Q):
    Query=list(map(int,input().split(" ")))
    l=len(A)
    if Query[0]==1:
        if l%2==0 :
            if Query[1]<A[int(l/2)-1]:
                min=min+A[int(l/2)-1]-Query[1]
            elif Query[1]>A[int(l/2)]:
                min=min+Query[1]-A[int(l/2)]
        else:
            min=int(abs(A[int((l-1)/2)]-Query[1]))
        j=0
        while Query[1]>A[j]:
            j=j+1
            if j>=l:
                break
        A.insert(j,Query[1])
        print(A)
        B=B+Query[2]
    else:
        s=int((l-1)/2)
        x=int(A[s])
        print(x,end=" ")
        print(int(min+B))

Submission status: Runtime Error

Solution code:
import numpy as np
Q=int(input())
def func(x,a,b):
    return int(abs(x-a)+b)
A=[]
B=[]
j=0
for i in range (0,Q):
    Query=list(map(int,input().split(" ")))
    if Query[0]==1:
        A=np.append(A,Query[1])
        B=np.append(B,Query[2])
        A=np.sort(A)
        j=j+1
    else:
        s=int((len(A)-1)/2)
        x=int(A[s])
        min=0
        for k in range(0,j):
            min=min+func(x,A[k],B[k])
        print(x,end=" ")
        print(min)
        A=[]
        B=[]
        j=0

Submission status: Runtime Error

Solution code:
import heapq

Q = int(input())
B = 0

q, a, b = map(int, input().split())
L, R = [-a], [a]
L_sum, R_sum = a, a
B = b

for i in range(Q - 1):
    q = list(map(int, input().split()))
    if len(q) == 3:
        A = q[1]
        B += q[2]

        if A <= -L[0]:
            heapq.heappush(L, -A)
            M = -heapq.heappushpop(L, -A)
            heapq.heappush(R, M)

            L_sum += (2 * A - M)
            R_sum += M
        else:
            heapq.heappush(R, A)
            M = heapq.heappush(R, A)
            heapq.heappush(L, -A)

            R_sum += (2 * A - M)
            L_sum += M
    else:
        N = len(L)
        X = -L[0]
        print(X, (abs(L_sum - X * N) + abs(R_sum - X * N)) // 2 + B)

Submission status: Runtime Error

Solution code:
from heapq import*
L,R=[]*2
B=t=0
Q,*E=open(0)
for e in E:
	if' 'in e:_,a,b=map(int,e.split());t=1-t;a*=2*t-1;c=heappushpop([L,R][t],a);heappush([R,L][t],-c);B+=b+a-c-c
	else:print(-L[0],B-L[0]*t)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import heapq


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    Q = int(input())
    sum_b = 0
    sum_al = 0
    sum_ar = 0
    hl = []
    hr = []
    for _ in range(Q):
        buf = input()
        if buf[0] == '1':
            _, a, b = map(int, buf.split())
            sum_b += b
            if len(hl) == 0:
                heapq.heappush(hl, -a)
                sum_al += a
                continue
            if len(hr) == 0:
                heapq.heappush(hr, a)
                sum_ar += a
                if -hl[0] > hr[0]:
                    hl[0], hr[0] = -hr[0], -hl[0]
                    sum_al, sum_ar = sum_ar, sum_al
                continue

            if a < -hl[0]:
                heapq.heappush(hl, -a)
                sum_al += a
            elif a > hr[0]:
                heapq.heappush(hr, a)
                sum_ar += a
            else:
                #if len(hl) <= len(hr):
                heapq.heappush(hl, -a)
                sum_al += a
                #else:
                #    heapq.heappush(hr, a)

            while len(hr) > len(hl):
                tmp = heapq.heappop(hr)
                sum_ar -= tmp
                heapq.heappush(hl, -tmp)
                sum_al += tmp
            while len(hl) > len(hl)+1:
                tmp = heapq.heappop(hl)
                sum_al -= tmp
                heapq.heappush(hr, -tmp)
                sum_ar += tmp

        else:
            tmp_al = -hl[0]*len(hl)-sum_al if len(hl) != 0 else 0
            tmp_ar = sum_ar-(-hl[0])*len(hr) if len(hl) != 0 else 0
            print(hl, sum_al, hr, sum_ar)
            print(-hl[0], tmp_al+tmp_ar+sum_b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from statistics import median
q0=int(input())
ind=0
a=[]
b=[]
for iii in range(q0):
  q=[int(_) for _ in input().split()]
  lenq=len(q)
  if lenq==1:
    meda=median(a)
    ind=sum([abs(_a-meda) for _a in a])+sum(b)
    i=1
    while sum([abs(_a-i-meda) for _a in a])+sum(b)==ind:
      i+=1
    print(int(meda-i+1),int(ind))
  elif lenq==3:
    a.append(q[1])
    b.append(q[2])

Submission status: Runtime Error

Solution code:
from heapq import *

Q = int(input())

lows = []
highs = []

a = []
b = 0
r = 0

for i in range(Q):
    vs = [int(_) for _ in input().split()]
    if vs[0] == 1:
        b = +vs[2]
        if not lows:
            heappush(lows, -vs[1])
        else:
            r += abs(vs[1] + lows[0])
            if vs[1] <= -lows[0]:
                heappush(lows, -vs[1])
            else:
                heappush(highs, vs[1])
        
        if len(lows) < len(highs):
            x = heappop(highs)
            y = -lows[0]
            r += y - x
            heappush(lows, -x)
            
        elif len(lows) > len(highs) + 1:
            x = -heappush(lows)
            if len(highs):
                y = highs[0]
            else:
                y = 0
            heappush(highs,x)
    else:
        print(-lows[0], r+b)

Submission status: Runtime Error

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
  
def solve():
    Q = int(single_input())
    n, a, b = map(int, line_input())
    left, right = collections.deque([a]), collections.deque([a])
    minans =  b
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            if left[-1] <= a <= right[0]:
                left.append(a)
                right.appendleft(a)
            elif a < left[-1]:
                minans += left[-1] - a
                insertpos = bisect_left(left, a)
                left.insert(insertpos, a)
                left.insert(insertpos, a)
                right.appendleft(left.pop())
            else:
                minans += a - right[0]
                insertpos = bisect_left(right, a)
                right.insert(insertpos, a)
                right.insert(insertpos, a)
                left.append(right.popleft())
        else: print(left[-1], minans)
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

qn = int(input())

low = []
high = []
ans = 0
num = 0

for i in range(qn):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        ans += q[2]
        a = q[1]
        if a < -low[0]:
            ans += -low[0] - a
        elif a > high[0]:
            ans += a - high[0]

        # lowは降順に並べたいので-aを入れる
        heappush(low, -a)
        heappush(high, a)
        if -low[0] > high[0]:
            low0 = heappop(low)
            high0 = heappop(high)
            # lowとhighで正負が逆なので注意する
            heappush(low, -high0)
            heappush(high, -low0)
    elif q[0] == 2:
        print(-low[0], ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heappushpop
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(R, -heappushpop(L, -q[1]))
        else:
            heappush(R, q[1])
            heappush(L, -heappushpop(R, Q[1]))
    else:
        print(-L[0], B+M)

Submission status: Runtime Error

Solution code:
from heapq import heappush 
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1]))
        heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -L[0], -R[0]
        heappush(R, q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -L[0], -R[0]
        assert -min(L) <= min(R)
    else:
        print(-L[0], B+M)

Submission status: Runtime Error

Solution code:
from heapq import heappush 
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1]))
        heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -L[0], -R[0]
        heappush(R, q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -L[0], -R[0]
        assert max(L) <= min(R)
    else:
        print(-L[0], B+M)

Submission status: Runtime Error

Solution code:
from collections import deque
Q = int(input())
S = []
L = []
CO = 0
MIN = 0
for i in range(Q):
    LI = list(map(int,input().split()))
    if LI[0] == 1:
        CO += LI[2]
        if len(S) == len(L):
            if len(S) == 0:
                S.append(LI[1])
            elif LI[1] <= L[0]:
                if LI[1] < S[-1]:
                    MIN += S[-1] - LI[1]
                S.append(LI[1])
                S.sort()
            else:
                MIN += LI[1] - L[0]
                S.append(L[0])
                L.pop(0)
                L.append(LI[1])
                L.sort()
        else:
            if LI[1] < S[-1]:
                MIN += S[-1] - LI[1]
                L.insert(0,S[-1])
                S.pop(-1)
                S.append(LI[1])
                S.sort()
            else:
                MIN += L[0] - S[-1]
                L.append(LI[1])
                L.sort()
    else:
        print(str(S[-1])+' '+str(MIN+CO))

Submission status: Runtime Error

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

# bit = Bit(10)
# bit.add(1, 1)
# bit.add(1, 1)

# # bit.add(2, 2)
# # bit.add(3, 3)
# print(bit.sum(1))

N=int(input())
queries = [tuple(map(int, input().split())) for _ in range(N)]

numl = []
for q in queries:
    if q[0] == 1:
        numl.append(q[1])
numl.sort()
val_to_key = {}

for i,v in enumerate(numl):
    if not v in val_to_key:
        val_to_key[v] = i

# print(numl)
# print(val_to_key)

cum_b = 0
cum_a = 0
bit = Bit(200005)
bit2 = Bit(200005)
cnt = 0

def abs_sum(mid):
    loc_sum = bit.sum(mid)
    lft_cnt = bit2.sum(mid)
    lef_sum = numl[mid]*lft_cnt - loc_sum
    rig_sum = cum_a-loc_sum - numl[mid]*(cnt-lft_cnt)
    return lef_sum + rig_sum

def solve():
    left = 0
    right = len(numl)-1
    while left < right:
        mid = left + right // 2
        diff = abs_sum(mid+1) - abs_sum(mid)
        if diff < 0:
            left = mid + 1
        else:
            right = mid
    return numl[left], abs_sum(left)+cum_b

for qu in queries:
    if qu[0] ==  1:
        _, a, b = qu
        bit.add(val_to_key[a], a)
        bit2.add(val_to_key[a], 1)
        cnt += 1
        cum_b += b
        cum_a += a
    else:
        sol, val = solve()
        print("{} {}".format(sol, val))

# cum = 0
# lis = []
# for _ in range(N):
#     qu=list(map(int, input().split()))
#     if qu[0] == 1:
#         lis.append(qu[1])
#         cum += qu[2]
#     else:

Submission status: Runtime Error

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

# bit = Bit(10)
# bit.add(1, 1)
# bit.add(1, 1)

# # bit.add(2, 2)
# # bit.add(3, 3)
# print(bit.sum(1))

N=int(input())
queries = [tuple(map(int, input().split())) for _ in range(N)]

numl = []
for q in queries:
    if q[0] == 1:
        numl.append(q[1])
numl.sort()
val_to_key = {}

for i,v in enumerate(numl):
    if not v in val_to_key:
        val_to_key[v] = i

# print(numl)
# print(val_to_key)

cum_b = 0
cum_a = 0
bit = Bit(100005)
bit2 = Bit(100005)
cnt = 0

def abs_sum(mid):
    loc_sum = bit.sum(mid)
    lft_cnt = bit2.sum(mid)
    lef_sum = numl[mid]*lft_cnt - loc_sum
    rig_sum = cum_a-loc_sum - numl[mid]*(cnt-lft_cnt)
    return lef_sum + rig_sum

def solve():
    left = 0
    right = len(numl)-1
    while left < right:
        mid = left + right // 2
        diff = abs_sum(mid+1) - abs_sum(mid)
        if diff < 0:
            left = mid + 1
        else:
            right = mid
    return numl[left], abs_sum(left)+cum_b

for qu in queries:
    if qu[0] ==  1:
        _, a, b = qu
        bit.add(val_to_key[a], a)
        bit2.add(val_to_key[a], 1)
        cnt += 1
        cum_b += b
        cum_a += a
    else:
        sol, val = solve()
        print("{} {}".format(sol, val))

# cum = 0
# lis = []
# for _ in range(N):
#     qu=list(map(int, input().split()))
#     if qu[0] == 1:
#         lis.append(qu[1])
#         cum += qu[2]
#     else:

Submission status: Runtime Error

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

Q = int(input())
ans = []
b = 0
ab = []
def ab_sum(a, center):
    length = len(a)
    a.sort()
    if length == 2:
        center = 0
        return a[1] - a[0]
    elif length == 1:
        center = 0
        return 0
    elif length % 2 == 0:
        center = (length-2)/2
        return sum(a[1+center:]) - sum(a[:center])
    else:
        center = length // 2
        return sum(a[center+1:]) - sum(a[:center])




for i in range(Q):
    a = list(map(int, input().split()))
    
    if len(a) == 1:
        
        ab.sort()
        center = 0
        ss = ab_sum(ab, center)
            
        print(ab[center] ,b + ss)
    else:
        b += a[2]
        ab.append(a[1])

Submission status: Runtime Error

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

Q = int(input())
ans = []
b = 0
ab = []
def ab_sum(a, center):
    length = len(a)
    a.sort()
    if length == 2:
        center = 0
        return a[1] - a[0]
    elif length == 1:
        center = 0
        return 0
    elif length % 2 == 0:
        center = length/2
        return sum(a[1+center:]) - sum(a[:center])
    else:
        center = length // 2
        return sum(a[center+1:]) - sum(a[:center])




for i in range(Q):
    a = list(map(int, input().split()))
    
    if len(a) == 1:
        
        ab.sort()
        center = 0
        ss = ab_sum(ab, center)
            
        print(ab[center] ,b + ss)
    else:
        b += a[2]
        ab.append(a[1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
from bisect import insort_left
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

Q=INT()

li=deque()
A=B=fx=cost=cnt=l=r=0
for _ in range(Q):
    instr=input()
    if instr[0]=='1':
        _,a,b=map(int, instr.split())
        B+=b
        insort_left(li, a)
        if cnt==0:
            l=r=A=a
        else:
            if not (l<=a<=r):
                cost+=min(abs(l-a), abs(r-a))
            # 偶数回目
            if cnt%2==1:
                A=l=li[len(li)//2-1]
                r=li[len(li)//2]
            # 奇数回目
            else:
                A=l=r=li[len(li)//2]
        fx=cost+B
        cnt+=1
    else:
        print(A, fx)

Submission status: Runtime Error

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

def foo(x):
    sum = 0
    for y in a:
        sum += abs(y-x)
    return sum+b

a = []
b = 0
q = inn()
for i in range(q):
    x = inl()
    if len(x)==1:
        z = (len(a)-1)//2
        print("{} {}".format(a[z],foo(a[z])))
    else:
        z = x[1]
        if a[-1] <= z:
            a.append(z)
        elif z <= a[0]:
            a.insert(0,z)
        else:
            up = len(a)-1
            lo = 0
            while lo+1 < up:
                mid = (lo+up)//2
                if z < a[mid]:
                    up = mid
                else:
                    lo = mid
            a.insert(up,z)
            b += x[2]