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

Solution (Python):
import heapq
Q = int(input())

heapL, heapR = [], []
s = 0
x = None
for i in range(Q):
    q = list(map(int, input().split()))
    if len(q) == 1:
        print(x, s)
    else:
        _, a, b = q
        s += b
        if not heapL:
            heapq.heappush(heapL, -a)
        elif not heapR:
            s += abs(a + heapL[0])
            heapq.heappush(heapR, -heapq.heappushpop(heapL, -a))
        else:
            if len(heapL) > len(heapR):
                s += abs(a + heapL[0])
                heapq.heappush(heapR, -heapq.heappushpop(heapL, -a))
            else:
                heapq.heappush(heapL, -heapq.heappushpop(heapR, a))
                s += abs(a + heapL[0])
        x = -heapL[0]

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from heapq import heappush, heappop

def main():
    q = II()
    Q = []
    for _ in range(q):
        Q.append(LI())
    lows, highs = [], []
    slow, shigh = 0, 0
    bias = 0
    for q in Q:
        if q[0] == 2:
            odd = -lows[0] if len(highs) != len(lows) else 0
            ans = -lows[0], bias + shigh - slow + odd
            print(*ans)
        else:
            _, a, b = q
            bias += b
            if not lows:
                lows = [-a]
                slow = a
            else:
                if a <= -lows[0]:
                    heappush(lows, -a)
                    slow += a
                    if len(lows) > len(highs) + 1:
                        x = -heappop(lows)
                        heappush(highs, x)
                        slow -= x
                        shigh += x
                else:
                    heappush(highs, a)
                    shigh += a
                    if len(highs) > len(lows):
                        x = heappop(highs)
                        heappush(lows, -x)
                        shigh -= x
                        slow += x
    return

main()

Solution (Python):
from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
ans = []
Q = int(readline())

QL = [10**10]
QR = [10**10]
R = 0

for i in range(Q):
    t, *A = map(int, input().split())
    if t == 1:
        a, b = A
        R += b
        if -QL[0] <= a <= QR[0]:
            heappush(QL, -a)
            heappush(QR, a)
        elif a <= -QL[0]:
            heappush(QL, -a)
            heappush(QL, -a)
            c = heappop(QL)
            R -= c + a
            heappush(QR, -c)
        elif QR[0] <= a:
            heappush(QR, a)
            heappush(QR, a)
            c = heappop(QR)
            R += a - c
            heappush(QL, -c)
    else:
        ans.append("%d %d\n" % (-QL[0], R))
sys.stdout.writelines(ans)

Solution (Python):
import heapq


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def absolute_minima():
    Q = int(input())

    L, R = PriorityQueue(), PriorityQueue()
    sL, sR = 0, 0
    M = None
    B = 0
    N = 0

    for _ in range(Q):
        query = [int(s) for s in input().split()]

        if query[0] == 1:
            _, a, b = query
            B += b
            N += 1

            if M is None:
                M = a
            elif M < a:
                R.enqueue(a)
                sR += a
            else:
                L.enqueue(-a)
                sL += a

            while len(R)-len(L) > 1:
                L.enqueue(-M)
                sL += M

                M = R.dequeue()
                sR -= M

            while len(L) > len(R):
                R.enqueue(M)
                sR += M

                M = -L.dequeue()
                sL -= M

        else:
            s = - sL + sR + B
            if N % 2 == 0:
                s -= M
            print(M, s)


if __name__ == "__main__":
    absolute_minima()

Solution (Python):
Q = int(input())
Queries = [list(map(int, input().split())) for _ in range(Q)]

import heapq as hp
L = [-(-(10**9+1))] 
R = [10**9+1] 
hp.heapify(L)
hp.heapify(R)
odd = False
sum_b = 0
sum_l = 0
sum_r = 0

for q in Queries:
  if len(q)==1 and q[0]==2:
    print(*(-L[0], sum_b + abs(sum_l-sum_r)))
    
  else:
    _, a, b = q
    sum_b += b

    l = -hp.heappop(L)
    r = hp.heappop(R)
    
    X = sorted([l, r, a])
    if odd==False:
      sum_l -= l
      sum_r -= r
      hp.heappush(L,-X[0])
      hp.heappush(L,-X[1])
      hp.heappush(R,X[2])
      sum_l += X[0]
      sum_r += X[2]
      odd=True
    elif odd==True:
      sum_r -= r
      hp.heappush(L,-X[0])
      hp.heappush(R,X[1])
      hp.heappush(R,X[2])
      sum_l += X[0]
      sum_r += X[1] + X[2]
      odd=False

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from heapq import heappush, heappop

def main():
    q = II()
    Q = []
    for _ in range(q):
        Q.append(LI())
    lows, highs = [], []
    slow, shigh = 0, 0
    bias = 0
    for q in Q:
        if q[0] == 2:
            odd = -lows[0] if len(highs) != len(lows) else 0
            ans = -lows[0], bias + shigh - slow + odd
            print(*ans)
        else:
            _, a, b = q
            bias += b
            if not lows:
                lows = [-a]
                slow = a
            else:
                if a <= -lows[0]:
                    heappush(lows, -a)
                    slow += a
                    if len(lows) > len(highs) + 1:
                        x = -heappop(lows)
                        heappush(highs, x)
                        slow -= x
                        shigh += x
                else:
                    heappush(highs, a)
                    shigh += a
                    if len(highs) > len(lows):
                        x = heappop(highs)
                        heappush(lows, -x)
                        shigh -= x
                        slow += x
    return

main()

Solution (Python):
import sys
input=sys.stdin.readline
from heapq import heappush,heappop
q=int(input())
_,a,b=map(int,input().split())
Small=[-a]; Large=[]
cnt=1
med=a
c=b
s=0
for i in range(q-1):
    query=tuple(map(int,input().split()))
    if query[0]==1:
        _,a,b=query
        c+=b
        if cnt%2:
            s+=abs(a-med)
            if a<-Small[0]:
                heappush(Small,-a)
                heappush(Large,-heappop(Small))
            else:
                heappush(Large,a)
        else:
            if a<=-Small[0]:
                heappush(Small,-a)
                med=-Small[0]
                s+=med-a
            elif a<=Large[0]:
                heappush(Small,-a)
            else:
                heappush(Large,a)
                med=heappop(Large)
                s+=a-med
                heappush(Small,-med)
        cnt+=1
        med=-Small[0]
    else:
        print(med,s+c)

Solution (Python):
from heapq import *

q = int(input())
b_cur = 0
diff = 0
lefts, rights = [], []

for i in range(q):
    query = input()
    if len(query) > 1:
        _, a, b = map(int, query.split())
        b_cur += b
        if len(lefts) == 0:
            heappush(lefts, -a)
        else:
            diff += abs(a + lefts[0])
            if a <= -lefts[0]:
                heappush(lefts, -a)
            else:
                heappush(rights, a)

        if len(lefts) < len(rights):
            med_r = heappop(rights)
            med_l = -lefts[0]
            diff += med_l - med_r
            heappush(lefts, -med_r)
        elif len(lefts) > len(rights)+1:
            med_l = -heappop(lefts)
            med_r = rights[0] if len(rights) > 0 else 0
            heappush(rights, med_l)
            
    else:
        print(-lefts[0], b_cur+diff)

Solution (Python):


import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()


class WHeap(object):
    def __init__(self):
        self._heap1 = []
        self._heap2 = []
        self.sum_h1 = 0
        self.sum_h2 = 0

    def __len__(self):
        return len(self._heap1) + len(self._heap2)

    def iter(self):
        for i in self._heap1:
            yield -i
        for i in self._heap2:
            yield i

    def __str__(self):
        return str(self._heap1) + " " + str(self._heap2)

    def push(self, n):
        if len(self) % 2 == 0:
            if not self._heap2 or n <= self._heap2[0]:
                heapq.heappush(self._heap1, -n)
                self.sum_h1 += n
            else:
                d = self._heap2[0]
                heapq.heappush(self._heap1, -heapq.heappop(self._heap2))
                self.sum_h1 += d
                self.sum_h2 -= d
                heapq.heappush(self._heap2, n)
                self.sum_h2 += n
        else:
            if n < -self._heap1[0]:
                d = -self._heap1[0]
                heapq.heappush(self._heap2, -heapq.heappop(self._heap1))
                self.sum_h1 -= d
                self.sum_h2 += d
                heapq.heappush(self._heap1, -n)
                self.sum_h1 += n
            else:
                heapq.heappush(self._heap2, n)
                self.sum_h2 += n

    def med(self):
        return -self._heap1[0]

    def pop(self, n):
        result = self.med()
        if len(self) % 2 == 0:
            heapq.heappop(self._heap1)
            heapq.heappush(self._heap1, -heapq.heappop(self._heap2))
        else:
            heapq.heappop(self._heap1)


def main():
    Q = II()
    wh = WHeap()
    B = 0
    for _ in range(Q):
        query = MIT()
        if query[0] == 1:
            wh.push(query[1])
            B += query[2]
        else:
            x = wh.med()
            if len(wh) % 2 == 0:
                f = - wh.sum_h1 + wh.sum_h2 + B
            else:
                f = x - wh.sum_h1 + wh.sum_h2 + B
            print(x, f)


if __name__ == "__main__":
    main()

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

N = int(input())
b_sum = 0
Q1 = []
Q = []
vars = []
for _ in range(N):
    Qu = list(map(int, input().split()))
    Q.append(Qu)
    if Qu[0]==1:
        _, a, b = Qu
        vars.append(a)
        
    else:
        pass
vars = list(set(vars))
vars.sort()
d = dict((v, i) for i, v in enumerate(vars))
lend = len(d)
bit = Bit(lend)
bit2 = Bit(lend)
n = 0
for q in Q:
    if q[0]==1:
        _, a, b = q
        bit.add(d[a], a)
        bit2.add(d[a], 1)
        b_sum += b
        n += 1
    else:
        l, r = 0, len(vars)
        con = (n - 1) >> 1
        while l+1 < r:
            c = (l+r)>>1
            cnt = bit2.sum(c)
            if cnt <= con:
                l = c
            else:
                r = c
        idx = l
        v = vars[idx]
        m = bit2.sum(idx)
        s = bit.sum(idx)
        m_ = bit2.sum(lend) - m
        s_ = bit.sum(lend) - s
        ans = b_sum + m*v-s + s_-m_*v
        print(v, ans)

Solution (Python):
import heapq

def main(): 
    smaller = []
    larger = []

    smallsum = 0
    largesum = 0

    const = 0

    q = int(input())
    for _ in range(q):
        inp = input()
        if inp[0] == '1':
            _,a,b = [int(x) for x in inp.split()]
            const += b

            if not smaller:
                smaller.append(-a)
                smallsum += a

            elif a <= -smaller[0]:
                heapq.heappush(smaller, -a)
                smallsum += a

            else:
                heapq.heappush(larger, a)
                largesum += a

            while len(smaller)>len(larger)+1:
                a = -heapq.heappop(smaller)
                smallsum -= a
                heapq.heappush(larger, a)
                largesum += a
            while len(larger)>len(smaller):
                a = heapq.heappop(larger)
                largesum -= a
                heapq.heappush(smaller,-a)
                smallsum += a

        else:
            x = (-smaller[0]) if smaller else (-10**9)
            print x, const + len(smaller)*x - smallsum + largesum - len(larger)*x











py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = sys.stdin.readline


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Solution (Python):


q0=int(input())
from heapq import *

low=[]
high=[]
ans=0
num=0
for _ in range(q0):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        ans+=q[2]
        num+=1
        a=q[1]
        if num==1:
            heappush(low,-a)
            df = 0
        elif num%2==1:
            centold = -low[0]
            centold2 = high[0]
            if -low[0] >= a:
                heappush(low,-a)
            else:
                c=heappushpop(high,a)
                heappush(low,-c)
            centnew = -low[0]
            if centnew < centold:
                df = 2*(centold-centnew)
            elif centnew <= centold2:
                df = 0
            else:
                df = 2*(centnew - centold2)
        else:
            centold = -low[0]
            if -low[0] > a:
                c=heappushpop(low,-a)
                heappush(high,-c)
            else:
                heappush(high,a)
            centnew = -low[0]
            if centnew < centold:
                df = (centold-centnew)
            else:
                df = (centnew - centold)
        df += abs(-low[0]-a)

        ans += df
            
        
        
        

    if q[0] == 2:
        print(-low[0],ans)

Solution (Python):
class BITree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def calc(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

Q=int(input())
query=[list(map(int,input().split())) for i in range(Q)]
tmp=[]
for i in range(Q):
    seq=query[i]
    if len(seq)==1:
        continue
    else:
        tmp.append((seq[1],i))
tmp.sort()
X=[(-1,-1) for i in range(Q)]
for i,sq in enumerate(tmp):
    X[sq[1]]=(i+1,sq[0])
N=len(tmp)
Idx=BITree(N)
Clc=BITree(N)
Btm=0
nowindex=0
for i in range(Q):
    if X[i]==(-1,-1):
        left=1
        right=N
        mid=(left+right)//2
        while(left<=right):
            mid=(left+right)//2
            if Idx.calc(mid)<(nowindex+1)//2:
                left=mid+1
            else:
                right=mid-1
        k=left
        x=(Clc.calc(k)-Clc.calc(k-1))
        ans=Clc.calc(N)-2*Clc.calc(k)-x*(Idx.calc(N)-2*Idx.calc(k))+Btm
        print(x,ans)
    else:
        Idx.add(X[i][0],1)
        Clc.add(X[i][0],X[i][1])
        Btm+=query[i][2]
        nowindex+=1

Solution (Python):
Q = int(input())

from heapq import *

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:
            x = vs[1]
            heappush(lows, -x)
        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 = -heappop(lows)
            y = highs[0] if len(highs) else 0
            heappush(highs, x)
            

        

    else:
        print(-lows[0], r + b)

Solution (Python):
import heapq
spq = []
bpq = []

small_sum=0
que_s_size=0
que_b_size=0

big_sum=0

Q=int(input())
ans = []
b_sum=0
for i in range(Q):
    q=input().split()    
    if len(q)>1:
        a=int(q[1])
        if que_s_size==0:
            heapq.heappush(spq,-a)
            small_sum+=a
            que_s_size+=1
        elif que_s_size>que_b_size:
            c=-heapq.heappop(spq)
            small_sum-=c
            if c>a:
                
                heapq.heappush(bpq,c)
                big_sum+=c
                heapq.heappush(spq,-a)
                
                small_sum+=a
            else:
                
                heapq.heappush(bpq,a)
                big_sum+=a
                
                heapq.heappush(spq,-c)
                small_sum+=c
            que_b_size+=1
        else:
            c=-heapq.heappop(spq)
            small_sum-=c
            d=heapq.heappop(bpq)
            big_sum-=d
            if a>d:
                
                heapq.heappush(bpq,a)
                big_sum+=a
                
                
                heapq.heappush(spq,-c)
                heapq.heappush(spq,-d)
                small_sum+=c+d
            else:
                
                heapq.heappush(bpq,d)
                big_sum+=d
                
                
                heapq.heappush(spq,-a)
                heapq.heappush(spq,-c)
                small_sum+=a+c
            que_s_size+=1

        b_sum+=int(q[2])
    else:
        if que_s_size>que_b_size:
            c=-heapq.heappop(spq)
            S = b_sum+big_sum-small_sum+c
            ans.append(str(c)+" "+str(S))
            
            heapq.heappush(spq,-c)
        else:
            c=-heapq.heappop(spq)
            S = b_sum+big_sum-small_sum
            ans.append(str(c)+" "+str(S))
            
            heapq.heappush(spq,-c)
            

for a in ans:
    print(a)

Solution (Python):
import heapq

q = int(input())


_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            
            heapq.heappush(a_small, -a)
            total += -(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            
            heapq.heappush(a_large, a)
            total += (a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        x = -a_small[0]
        print(x, total+cons)

Solution (Python):
from heapq import *

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    lower_heap = []
    higher_heap = []
    median = constant = sum_lower = sum_higher = 0
    for _ in range(read_int()):
        ar = read_int_array()
        if len(ar) == 3:
            constant += ar[2]
            x = ar[1]
            if not lower_heap:
                lower_heap.append(-x)
                sum_lower += x
                median = x
            elif not higher_heap:
                heappush(lower_heap, -x)
                sum_lower += x

                x = -heappop(lower_heap)
                sum_lower -= x
                heappush(higher_heap, x)
                sum_higher += x
                median = -lower_heap[0]
            elif x <= -lower_heap[0]:
                heappush(lower_heap, -x)
                sum_lower += x

                if len(lower_heap) - len(higher_heap) > 1:
                    x = -heappop(lower_heap)
                    sum_lower -= x
                    heappush(higher_heap, x)
                    sum_higher += x
                median = -lower_heap[0]
            else:
                heappush(higher_heap, x)
                sum_higher += x
                if len(higher_heap) > len(lower_heap):
                    x = heappop(higher_heap)
                    sum_higher -= x
                    heappush(lower_heap, -x)
                    sum_lower += x
                median = -lower_heap[0]
        else:
            write(median, constant + abs(sum_lower - median * len(lower_heap)) + abs(sum_higher - median * len(higher_heap)))
main()

Solution (Python):

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 solve():
    ok = len_memo
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if 2 * bit1.get(mid, len_memo) <= cnt :
            ok = mid
        else:
            ng = mid
    return memo_inv[ng]
    

def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    
    
    return memo, len(list2)

q = int(input())
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)
memo_inv = dict([(v,k) for k,v in memo.items()])




bit = BIT(len_memo)

bit1 = BIT(len_memo)

x = []
b = 0
cnt = 0
for i in range(q):
    if info[i][0] == 1:
        bit.add(memo[info[i][1]], info[i][1])
        bit1.add(memo[info[i][1]], 1)
        b += info[i][2]
        cnt += 1
    if info[i][0] == 2:
        median_x = solve()
        sum1 = bit.get(0, memo[median_x])
        num1 = bit1.get(0, memo[median_x])
        sum2 = bit.get(memo[median_x], len_memo)
        num2 = bit1.get(memo[median_x], len_memo)
        
        print(median_x, abs(num1*median_x - sum1) + abs(num2*median_x - sum2) + b)

Solution (Python):
import sys
import heapq

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

q = ni()

lh = []
hh = []
ln = 0
hn = 0
ls = 0
hs = 0
off = 0
for z in range(q):
    line = na()
    if line[0] == 1:
        _, a, b = line
        off += b

        if len(lh) > 0:
            mid = -lh[0]
            if a <= mid:
                heapq.heappush(lh, -a)
                ls += a
                ln += 1
            else:
                heapq.heappush(hh, a)
                hs += a
                hn += 1
        else:
            heapq.heappush(lh, -a)
            ls += a
            ln += 1

        while ln < hn:
            mx = heapq.heappop(hh)
            hs -= mx
            hn -= 1
            ls += mx
            ln += 1
            heapq.heappush(lh, -mx)

        while ln > hn + (ln+hn)%2:
            mx = -heapq.heappop(lh)
            ls -= mx
            ln -= 1
            heapq.heappush(hh, mx)
            hs += mx
            hn += 1
    else:
        lls = -lh[0]*ln - ls
        hhs = hs - (-lh[0]*hn)
        print(-lh[0], lls+hhs+off)

Solution (Python):
from collections import defaultdict as ddic, deque, Counter
from itertools import permutations, combinations, product
import bisect, heapq
import Queue as queue 
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

lower = []  
upper = []
sums = [0, 0]
def add(x):
    if len(lower) <= len(upper):
        heapq.heappush(lower, -x)
        sums[0] += x
    else:
        heapq.heappush(upper, x)
        sums[1] += x
    while lower and upper and -lower[0] > upper[0]:
        left = -heapq.heappop(lower)
        right = heapq.heappop(upper)
        sums[0] -= left
        sums[1] -= right
        heapq.heappush(lower, -right)
        heapq.heappush(upper, left)
        sums[0] += right
        sums[1] += left
    
    
B = [0]
def update(a, b):
    
    B[0] += b
    add(a)
    
def report():
    
    
    median = -lower[0]
    val = B[0]
    val += len(lower) * median - sums[0]
    val += sums[1] - len(upper) * median
    return median, val
    

Q = rri()
for _ in xrange(Q):
    query = rrm()
    if query[0] == 1:
        update(query[1], query[2])
    else:
        m,v = report()
        print m, v