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):
from heapq import heappop, heappush
class MedianContainer:
    def __init__(self):
        self._left_q = []
        self._right_q = []
        self._left_sum = 0
        self._right_sum = 0
        self._med1, self._med2 = None, None
        self._med = None

    def insert(self, x):
        if not any([self._med, self._med1, self._med2]): 
            self._med = x
        elif self._med is None and self._med1 is not None and self._med2 is not None:
            if x <= self._med1:
                heappush(self._left_q, x*(-1))
                heappush(self._right_q, self._med2)
                self._left_sum += x
                self._right_sum += self._med2
                self._med = self._med1
            elif x >= self._med2:
                heappush(self._left_q, self._med1*(-1))
                heappush(self._right_q, x)
                self._left_sum += self._med1
                self._right_sum += x
                self._med = self._med2
            else:
                heappush(self._left_q, self._med1*(-1))
                heappush(self._right_q, self._med2)
                self._left_sum += self._med1
                self._right_sum += self._med2
                self._med = x
            self._med1, self._med2 = None, None
        else:
            if x <= self._med:
                heappush(self._left_q, x*(-1))
                self._med1 = heappop(self._left_q)*(-1)
                self._left_sum += x
                self._left_sum -= self._med1
                self._med2 = self._med
            else:
                heappush(self._right_q, x)
                self._right_sum += x
                self._med1 = self._med
                self._med2 = heappop(self._right_q)
                self._right_sum -= self._med2
            self._med = None

        
    def get_med(self):
        if self._med is not None:
            return [self._med]
        else:
            return [self._med1, self._med2]


    def get_left_sum(self):
        return self._left_sum


    def get_right_sum(self):
        return self._right_sum


    def get_half_len(self):
        return len(self._left_q)


q = int(input())
ans = 0

mid_1 = 0
mid_2 = 0
mid = 0
left_q = []
right_q = []
left_sum = 0
right_sum = 0
const_b = 0
ansl = []

mc = MedianContainer()
for _ in range(q):
    row = list(input().split())
    if row[0] == '2':
        half_len = mc.get_half_len()
        meds = mc.get_med()
        if len(meds) == 1:
            left_sum = meds[0]*half_len - mc.get_left_sum()
            right_sum = mc.get_right_sum() - meds[0]*half_len
            ans = left_sum + right_sum + const_b
            ansl.append((meds[0],ans))
        else:
            left_sum = meds[0]*half_len - mc.get_left_sum()
            right_sum = mc.get_right_sum() - meds[0]*half_len
            ans = left_sum + right_sum + (meds[1]-meds[0]) + const_b
            ansl.append((meds[0],ans))
    
    else:
        a,b = int(row[1]), int(row[2])
        const_b += b
        mc.insert(a)


for ax,av in ansl:
    print(ax,av)

Solution (Python):
from heapq import heappop, heappush

q = int(input())
ans = 0

mid_1 = 0
mid_2 = 0
mid = 0
left_q = []
right_q = []
left_sum = 0
right_sum = 0
const_b = 0
ansl = []

first_flag = True
double_mid = False
for _ in range(q):
    row = list(input().split())
    if row[0] == '2':
        half_n = len(left_q)
        if double_mid:
            q_left_sum = mid_1*half_n - left_sum
            q_right_sum = right_sum - mid_1*half_n
            ans_v = q_left_sum + q_right_sum + (mid_2-mid_1) + const_b
            ans_x = mid_1
            ansl.append((ans_x, ans_v))
        else:
            q_left_sum = mid*half_n - left_sum
            q_right_sum = right_sum - mid*half_n
            ans_v = q_left_sum + q_right_sum + const_b
            ans_x = mid
            ansl.append((ans_x, ans_v))
    
    else:
        a,b = int(row[1]), int(row[2])
        const_b += b

        if first_flag:
            mid = a
            first_flag = False

        elif double_mid:
            double_mid = False
            if a <= mid_1:
                heappush(left_q, a*(-1))
                left_sum += a
                heappush(right_q, mid_2)
                right_sum += mid_2
                mid = mid_1
            elif a >= mid_2:
                heappush(left_q, mid_1*(-1))
                left_sum += mid_1
                heappush(right_q, a)
                right_sum += a
                mid = mid_2
            else:
                heappush(left_q, mid_1*(-1))
                left_sum += mid_1
                heappush(right_q, mid_2)
                right_sum += mid_2
                mid = a
            
            


        else:
            double_mid = True
            if a <= mid:
                heappush(left_q, a*(-1))
                left_sum += a
                mid_1 = heappop(left_q)*(-1)
                left_sum -= mid_1
                mid_2 = mid
            else:
                heappush(right_q, a)
                right_sum += a
                mid_1 = mid
                mid_2 = heappop(right_q)
                right_sum -= mid_2
            
            



for ax,av in ansl:
    print(ax,av)

Solution (Python):
class BalancingTree:
    def __init__(self, n,id=0):
        self.N = n
        self.id_size=id
        self.root = self.node(1<<(n+self.id_size), 1<<(n+self.id_size),self.id_size)
        self.val_dic={}

    def debug(self):
        def debug_info(nd_):
            return (nd_.value,(nd_.value - 1)>>self.id_size, nd_.pivot , nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1,nd_.cnt)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def rebuild(self,v):
        self.id_size+=1
        
        self.root=self.node(1<<(self.N+self.id_size), 1<<(self.N+self.id_size),self.id_size)
        check=[]
        for val in self.val_dic:
            cnt=self.val_dic[val]
            self.val_dic[val]=0
            for j in range(cnt):
                self.append(val)
        self.append(v)

    def append(self,v):
        if v not in self.val_dic:
            self.val_dic[v]=0
        id=self.val_dic[v]
        if id>=2**self.id_size:
            self.rebuild(v)
        else:
            V=(v<<self.id_size)+id
            self.val_dic[v]+=1
            self._append(V)

    def _append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                return 0
            else:
                nd.cnt+=1
                nd.sum+=(v-1)>>self.id_size
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2,self.id_size)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2,self.id_size)
                        break

    def kth(self,k):
        cnt=k
        nd=self.root
        while True:
            if nd.left:
                if nd.left.cnt<k:
                    k-=nd.left.cnt+1
                    if nd.right:
                        nd=nd.right
                    else:
                        raise IndexError("BalancingTree doesn't hold kth number")
                elif nd.left.cnt==k:
                    return (nd.value-1)>>self.id_size
                else:
                    nd=nd.left
            else:
                if k==0:
                    return (nd.value-1)>>self.id_size
                if nd.right:
                    k-=1
                    nd=nd.right
                else:
                    raise IndexError("BalancingTree doesn't hold kth number")

    def kth_sum(self,k):
        if k==-1:
            return 0
        cnt=k
        res_sum=0
        nd=self.root
        while True:
            if nd.left:
                if nd.left.cnt<k:
                    k-=nd.left.cnt+1
                    res_sum+=nd.left.sum+((nd.value-1)>>self.id_size)
                    if nd.right:
                        nd=nd.right
                    else:
                        raise IndexError("BalancingTree doesn't hold kth number")
                elif nd.left.cnt==k:
                    res_sum+=nd.left.sum+((nd.value-1)>>self.id_size)
                    return res_sum,(nd.value-1)>>self.id_size
                else:
                    nd=nd.left
            else:
                if k==0:
                    return res_sum+((nd.value-1)>>self.id_size),(nd.value-1)>>self.id_size
                if nd.right:
                    k-=1
                    res_sum+=((nd.value-1)>>self.id_size)
                    nd=nd.right
                else:
                    print(cnt,self.size,nd.value-1,nd.right)
                    self.debug()
                    raise IndexError("BalancingTree doesn't hold kth number")

    def kth_sum_big(self,k):
        res_sum=self.sum
        if self.size>k:
            res_sum-=self.kth_sum(self.size-k-2)
            return res_sum
        else:
            raise IndexError("BalancingTree doesn't hold kth number")

    def leftmost(self, nd):
        while nd.left:
            nd=nd.left
        return nd

    def rightmost(self, nd):
        while nd.right:
            nd=nd.right
        return nd

    def find_l(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return (prev - 1)>>self.id_size
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return (prev - 1)>>self.id_size

    def find_r(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return (prev - 1)>>self.id_size
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return (prev - 1)>>self.id_size

    @property
    def max(self):
        if self.size:
            return self.find_l((1<<(self.N+self.id_size))-1)
        return 0

    @property
    def min(self):
        if self.size:
            return self.find_r(-1)
        return 0

    @property
    def sum(self):
        return self.root.sum-((self.root.value-1)>>self.id_size)

    @property
    def size(self):
        return self.root.cnt-1

    def delete(self,v):
        id=self.val_dic[v]-1
        if id==-1:
            raise IndexError("You are an idiot")
        V=(v<<self.id_size)+id
        self._delete(V)
        self.val_dic[v]-=1

    def _delete(self, v, nd = None, prev = None):
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            nd.cnt-=1
            nd.sum-=(v-1)>>self.id_size
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        nd.cnt-=1
        nd.sum-=(v-1)>>self.id_size
        if (not nd.left) and (not nd.right):
            if not prev.left:
                prev.right=None
            elif not prev.right:
                prev.left=None
            else:
                if nd.pivot==prev.left.pivot:
                    prev.left=None
                else:
                    prev.right=None
        elif nd.right:
            nd.value = self.leftmost(nd.right).value
            self._delete(nd.value - 1, nd.right, nd)
        else:
            nd.value = self.rightmost(nd.left).value
            self._delete(nd.value - 1, nd.left, nd)


    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    def __len__(self):
        return self.size

    class node:
        def __init__(self, v, p, m):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None
            self.cnt=1
            self.sum=(v-1)>>m

import sys

input=sys.stdin.readline

A=BalancingTree(31,18)
B=0
S=0

for _ in range(int(input())):
    q=list(map(int,input().split()))
    if q[0]==1:
        a,b=q[1:]
        A.append(a+10**9)
        B+=b
        S+=a
    else:
        n=A.size
        smallsum,mid=A.kth_sum((n+1)//2-1)
        mid-=10**9
        smallsum-=((n+1)//2)*10**9
        print(mid,S-2*smallsum+B+(n%2)*mid)

Solution (Python):
class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.id_size=0
        self.root = self.node(1<<(n+self.id_size), 1<<(n+self.id_size),self.id_size)
        self.val_dic={}

    def debug(self):
        def debug_info(nd_):
            return (nd_.value,(nd_.value - 1)>>self.id_size, nd_.pivot , nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1,nd_.cnt)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def rebuild(self,v):
        self.id_size+=1
        
        self.root=self.node(1<<(self.N+self.id_size), 1<<(self.N+self.id_size),self.id_size)
        check=[]
        for val in self.val_dic:
            cnt=self.val_dic[val]
            self.val_dic[val]=0
            for j in range(cnt):
                self.append(val)
        self.append(v)

    def append(self,v):
        if v not in self.val_dic:
            self.val_dic[v]=0
        id=self.val_dic[v]
        if id>=2**self.id_size:
            self.rebuild(v)
        else:
            V=(v<<self.id_size)+id
            self.val_dic[v]+=1
            self._append(V)

    def _append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                return 0
            else:
                nd.cnt+=1
                nd.sum+=(v-1)>>self.id_size
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2,self.id_size)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2,self.id_size)
                        break

    def kth(self,k):
        cnt=k
        nd=self.root
        while True:
            if nd.left:
                if nd.left.cnt<k:
                    k-=nd.left.cnt+1
                    if nd.right:
                        nd=nd.right
                    else:
                        raise IndexError("BalancingTree doesn't hold kth number")
                elif nd.left.cnt==k:
                    return (nd.value-1)>>self.id_size
                else:
                    nd=nd.left
            else:
                if k==0:
                    return (nd.value-1)>>self.id_size
                if nd.right:
                    k-=1
                    nd=nd.right
                else:
                    raise IndexError("BalancingTree doesn't hold kth number")

    def kth_sum(self,k):
        if k==-1:
            return 0
        cnt=k
        res_sum=0
        nd=self.root
        while True:
            if nd.left:
                if nd.left.cnt<k:
                    k-=nd.left.cnt+1
                    res_sum+=nd.left.sum+((nd.value-1)>>self.id_size)
                    if nd.right:
                        nd=nd.right
                    else:
                        raise IndexError("BalancingTree doesn't hold kth number")
                elif nd.left.cnt==k:
                    res_sum+=nd.left.sum+((nd.value-1)>>self.id_size)
                    return res_sum,(nd.value-1)>>self.id_size
                else:
                    nd=nd.left
            else:
                if k==0:
                    return res_sum+((nd.value-1)>>self.id_size),(nd.value-1)>>self.id_size
                if nd.right:
                    k-=1
                    res_sum+=((nd.value-1)>>self.id_size)
                    nd=nd.right
                else:
                    print(cnt,self.size,nd.value-1,nd.right)
                    self.debug()
                    raise IndexError("BalancingTree doesn't hold kth number")

    def kth_sum_big(self,k):
        res_sum=self.sum
        if self.size>k:
            res_sum-=self.kth_sum(self.size-k-2)
            return res_sum
        else:
            raise IndexError("BalancingTree doesn't hold kth number")

    def leftmost(self, nd):
        while nd.left:
            nd=nd.left
        return nd

    def rightmost(self, nd):
        while nd.right:
            nd=nd.right
        return nd

    def find_l(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return (prev - 1)>>self.id_size
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return (prev - 1)>>self.id_size

    def find_r(self, v):
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return (prev - 1)>>self.id_size
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return (prev - 1)>>self.id_size

    @property
    def max(self):
        if self.size:
            return self.find_l((1<<(self.N+self.id_size))-1)
        return 0

    @property
    def min(self):
        if self.size:
            return self.find_r(-1)
        return 0

    @property
    def sum(self):
        return self.root.sum-((self.root.value-1)>>self.id_size)

    @property
    def size(self):
        return self.root.cnt-1

    def delete(self,v):
        id=self.val_dic[v]-1
        if id==-1:
            raise IndexError("You are an idiot")
        V=(v<<self.id_size)+id
        self._delete(V)
        self.val_dic[v]-=1

    def _delete(self, v, nd = None, prev = None):
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            nd.cnt-=1
            nd.sum-=(v-1)>>self.id_size
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        nd.cnt-=1
        nd.sum-=(v-1)>>self.id_size
        if (not nd.left) and (not nd.right):
            if not prev.left:
                prev.right=None
            elif not prev.right:
                prev.left=None
            else:
                if nd.pivot==prev.left.pivot:
                    prev.left=None
                else:
                    prev.right=None
        elif nd.right:
            nd.value = self.leftmost(nd.right).value
            self._delete(nd.value - 1, nd.right, nd)
        else:
            nd.value = self.rightmost(nd.left).value
            self._delete(nd.value - 1, nd.left, nd)


    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    def __len__(self):
        return self.size

    class node:
        def __init__(self, v, p, m):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None
            self.cnt=1
            self.sum=(v-1)>>m

import sys

input=sys.stdin.readline

A=BalancingTree(31)
B=0
S=0

for _ in range(int(input())):
    q=list(map(int,input().split()))
    if q[0]==1:
        a,b=q[1:]
        A.append(a+10**9)
        B+=b
        S+=a
    else:
        n=A.size
        smallsum,mid=A.kth_sum((n+1)//2-1)
        mid-=10**9
        smallsum-=((n+1)//2)*10**9
        print(mid,S-2*smallsum+B+(n%2)*mid)

Solution (Python):
import sys

input=sys.stdin.readline

Q=int(input())
ques=[[] for i in range(0,Q)]
value=set([])
for i in range(0,Q):
    ques[i]=list(map(int,input().split()))
    if ques[i][0]==1:
        value.add(ques[i][1])

value=list(value)
value.sort()
n=len(value)
dic={}
for i in range(n):
    dic[value[i]]=0
    dic[value[i]]=i


def segfunc(x,y):
    return x+y

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele =0


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

index=dic[ques[0][1]]
update(index,1)
minx=ques[0][1]
minf=0
B=ques[0][2]
count=1
for i in range(1,Q):
    if ques[i][0]==2:
        print(minx,minf+B)
    else:
        a=ques[i][1]
        b=ques[i][2]
        index=dic[a]
        count+=1
        B+=b
        minf+=abs(a-minx)
        update(index,seg[index+num-1]+1)
        start=0
        end=n-1
        while end-start>1:
            test=(end+start)//2
            if query(0,test+1)>=(count+1)//2:
                end=test
            else:
                start=test

        if query(0,start+1)>=(count+1)//2:
            t=start
        else:
            t=end

        if value[t]>minx:
            if count%2==1:
                minf-=value[t]-minx
                minx=value[t]
            else:
                minf-=2*(value[t]-minx)
                minx=value[t]
        elif minx>value[t]:
            if count%2==1:
                minf-=value[t]-minx
                minx=value[t]
            else:
                minx=value[t]