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 sys
from heapq import heappush, heappop

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

Q = INT()
_, a, b = MAP()
mid = a
asm = 0
bsm = b
ln = 1
que1, que2 = [-a], [INF]
for _ in range(Q-1):
    li = LIST()
    if li[0] == 1:
        a, b = li[1:]
        bsm += b
        l = -que1[0]
        r = que2[0]
        if ln % 2 == 1:
            asm += abs(a - l)
            if a < mid:
                heappush(que1, -a)
                heappush(que2, -que1[0])
                heappop(que1)
            else:
                heappush(que2, a)
        else:
            if a < l:
                asm += abs(a - l)
            elif a > r:
                asm += abs(a - r)
            if a > mid:
                heappush(que2, a)
                heappush(que1, -que2[0])
                heappop(que2)
            else:
                heappush(que1, -a)
        ln += 1
        mid = -que1[0]
    else:
        print(mid, asm + bsm)

Solution (Python):


import sys
from heapq import heappush, heappop

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

Q = INT()
_, a, b = MAP()
mid = a
asm = 0
bsm = b
ln = 1
que1, que2 = [-a], [INF]
for _ in range(Q-1):
    li = LIST()
    if li[0] == 1:
        a, b = li[1:]
        bsm += b
        l = -que1[0]
        r = que2[0]
        if ln % 2 == 1:
            asm += abs(a - l)
            if a < mid:
                heappush(que1, -a)
                heappush(que2, -que1[0])
                heappop(que1)
            else:
                heappush(que2, a)
        else:
            if a < l:
                asm += abs(a - l)
            elif a > r:
                asm += abs(a - r)
            if a > mid:
                heappush(que2, a)
                heappush(que1, -que2[0])
                heappop(que2)
            else:
                heappush(que1, -a)
        ln += 1
        mid = -que1[0]
    else:
        print(mid, asm + bsm)

Solution (Python):
import heapq

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

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

L = []
R = []
pop = heapq.heappop
push = heapq.heappush
A, B, C = 0, 0, 0

def nasu(a):
  global A
  global C
  if len(R) == 0:
    push(R, a)
    C = a
    return
  if len(L) == 0:
    r = pop(R)
    push(L, -min(a, r))
    push(R, max(a, r))
    A += abs(a - r)
    C = min(a, r)
    return
  if len(L) < len(R):
    r = pop(R)
    l = -pop(L)
    push(L, -l)
    push(L, -min(a, r))
    push(R, max(a, r))
    A += abs(a - r)
    if a < l:
      C = l
    elif a < r:
      C = a
    return
  l = -pop(L)
  r = pop(R)
  if l <= a and a <= r:
    push(L, -l)
    push(R, r)
    push(R, a)
    C = a
  elif a < l:
    push(L, -a)
    push(R, r)
    push(R, l)
    A += abs(a - l)
    C = l
  else:
    push(L, -l)
    push(R, a)
    push(R, r)
    A += abs(a - r)
    C = r

for q in Query:
  if q[0] == 1:
    nasu(q[1])
    B += q[2]
  if q[0] == 2:
    print(C, A + B)

Solution (Python):
import heapq

q = int(input())

minheap = [] 
maxheap = [] 
heapq.heapify(minheap)
heapq.heapify(maxheap)

s = 0
m = 0

for _ in range(0, q):
    token = input().split()
    if len(token) > 1:
        a = int(token[1])
        b = int(token[2])
        s += b
        heapq.heappush(minheap, a)
        heapq.heappush(maxheap, -a)
        if -maxheap[0] > minheap[0]:
            maxv = -heapq.heappop(maxheap)
            minv = heapq.heappop(minheap)
            m += abs(maxv - minv)
            heapq.heappush(minheap, maxv)
            heapq.heappush(maxheap, -minv)
    else:
        print('{} {}'.format(-maxheap[0], s + m))

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

INF = 10**18

Q = int(input())
count = 0
s = 0

upper = [INF]
lower = [INF]
heapq.heapify(upper)
heapq.heapify(lower)

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0]==1:
        count += 1
        s += q[2]
        a = q[1]
        u = heapq.heappop(upper)
        l = -heapq.heappop(lower)
        if count%2==0:
            if a<l:
                heapq.heappush(lower,-a)
                heapq.heappush(upper,l)
                heapq.heappush(upper,u)
                s += l-a
            else:
                heapq.heappush(lower,-l)
                heapq.heappush(upper,a)
                heapq.heappush(upper,u)
                s += a-l
        else:
            if a<=u:
                heapq.heappush(lower,-l)
                heapq.heappush(lower,-a)
                heapq.heappush(upper,u)
                s += max(0,l-a)
            else:
                heapq.heappush(lower,-l)
                heapq.heappush(lower,-u)
                heapq.heappush(upper,a)
                s += a-u

    else:
        x = -heapq.heappop(lower)
        print(x,s)
        heapq.heappush(lower,-x)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i,x,bit):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum(i,bit):
        res = 0
        while i :
            res += bit[i]
            i -= i&-i
        return res
    Q = I()
    q = LIR(Q)
    bit = [0]*(Q+1)
    bit2  = [0]*(Q+1)
    bit3 = [0]*(Q+1)
    bit4 = [0]*(Q+1)
    A = []
    for qi in q:
        if qi[0] == 1:
            a = qi[1]
            A.append(a)
    qa = [i for i in A]
    qa.sort()
    ia = {i:bisect.bisect_left(qa,i) for i in A}
    revqa = [-i for i in qa[::-1]]
    revia = {i:bisect.bisect_left(revqa,-i) for i in A}
    sb = 0
    n = 0
    for qi in q:
        if qi[0] == 1:
            a,b = qi[1:]
            ia[a] += 1
            revia[a] += 1
            i = ia[a]
            revi = revia[a]
            add(i,1,bit)
            add(i,a,bit2)
            add(revi,1,bit3)
            add(revi,a,bit4)
            sb += b
            n += 1
        else:
            l = 0
            r = Q
            k = (n-1)>>1
            while r-l > 1:
                m = (l+r) >> 1
                if sum(m,bit) <= k:
                    l = m
                else:
                    r = m
            fa = qa[l]
            i = ia[fa]
            revi = revia[fa]
            s1 = sum(l,bit)
            s2 = sum(l,bit2)
            s3 = sum(revi,bit3)
            s4 = sum(revi,bit4)
            s = fa*s1-s2+s4-fa*s3+sb
            print(fa,s)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import heapq
import sys 
input = sys.stdin.readline

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

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

    r1 = a
    r2 = a

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

main()

Solution (Python):



import heapq

n = int(input())


l=[10**10]
r=[10**10]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0

ans = 0

for i in range(n):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if lenl>lenr:
            lenr+=1
            x = -l[0]
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(r,x)
                heapq.heapreplace(l,-q[1])
        else:
            lenl+=1
            x = r[0]
            if x<q[1]:
                heapq.heappush(l,-x)
                heapq.heapreplace(r,q[1])
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(-l[0]-q[1])
    if q[0]==2:
        print(-l[0], ans)

Solution (Python):
import heapq


n = int(input())
s = list(map(int, input().split()))


l=[]
r=[]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0


x = s[1]


ans = s[2]

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if lenl>=lenr:
            lenr+=1
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(r,x)
                x = -heapq.heappushpop(l,-q[1])
        else:
            lenl+=1
            if x<q[1]:
                heapq.heappush(l,-x)
                x = heapq.heappushpop(r,q[1])
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(x-q[1])
    if q[0]==2:
        print(x, ans)

Solution (Python):
import heapq

def main():
    n = int(input())
    s = list(map(int, input().split()))

    
    l=[]
    r=[]
    heapq.heapify(l)
    heapq.heapify(r)
    lenl=0
    lenr=0
    
    x = s[1]

    
    ans = s[2]

    for i in range(n-1):
        q = list(map(int,input().split()))
        if q[0]==1:
            ans += q[2]
            if (lenl+lenr)%2==0:
                lenr+=1
                ans+=abs(x-q[1])
                if x<=q[1]:
                    heapq.heappush(r,q[1])
                else:
                    heapq.heappush(l,-q[1])
                    heapq.heappush(r,x)
                    x = -heapq.heappop(l)
            else:
                lenl+=1
                if x<q[1]:
                    heapq.heappush(l,-x)
                    heapq.heappush(r,q[1])
                    x=heapq.heappop(r)
                else:
                    heapq.heappush(l,-q[1])
                ans+=abs(x-q[1])
        if q[0]==2:
            print(x, ans)
if __name__=="__main__":
    main()

Solution (Python):
import heapq

n = int(input())
s = list(map(int, input().split()))


l=[]
r=[]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0

x = s[1]


ans = s[2]

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if (lenl+lenr)%2==0:
            lenr+=1
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(l,-q[1])
                heapq.heappush(r,x)
                x = -heapq.heappop(l)
        else:
            lenl+=1
            if x<q[1]:
                heapq.heappush(l,-x)
                heapq.heappush(r,q[1])
                x=heapq.heappop(r)
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(x-q[1])
    if q[0]==2:
        print(x, ans)

Solution (Python):
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
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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
        self.total = 0

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

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

    def interval_sum(self, i, j):  
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total:
            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
        
        
        
        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(set(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:
        center_ind = bit1.search(n // 2 + bool(n % 2))
        d = n // 2 + bool(n % 2)
        min_val = bit2.interval_sum(center_ind + 1, bit2.size) - bit1.interval_sum(center_ind + 1, bit1.size) * \
                  ind_to_co[center_ind] + bit1.sum(center_ind - 1) * ind_to_co[center_ind] - bit2.sum(center_ind - 1) + B
        print(ind_to_co[center_ind], min_val)

Solution (Python):
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
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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
        self.total = 0

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

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

    def interval_sum(self, i, j):  
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total:
            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
        
        
        
        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(set(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))
        d = n // 2 + bool(n % 2)
        min_val = bit2.interval_sum(min_ind + 1, bit2.size) - bit1.interval_sum(min_ind + 1, bit1.size) * 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)

Solution (Python):
def main():
    import heapq
    left=[10**20]
    right=[10**20]
    heapq.heapify(left)
    heapq.heapify(right)
    q=int(input())
    ans=0
    cnt=0
    left_sum=0
    right_sum=0
    for _ in range(q):
        temp=input()
        if temp[0]=="1":
            cnt+=1
            x,a,b=map(int,temp.split())
            l=-heapq.heappop(left)
            r=heapq.heappop(right)
            left_sum-=l
            right_sum-=r
            ans+=b
            ll,aa,rr=sorted([l,a,r])
            heapq.heappush(right,rr)
            right_sum+=rr
            heapq.heappush(left,-ll)
            left_sum+=ll
            if len(left)==len(right):
                heapq.heappush(left,-aa)
                left_sum+=aa
            else:
                heapq.heappush(right,aa)
                right_sum+=aa
        else:
            i=-heapq.heappop(left)
            left_sum-=i
            print(i,ans+(right_sum-(len(right)-1)*i)+((len(left)-1)*i-left_sum))
            heapq.heappush(left,-i)
            left_sum+=i
main()

Solution (Python):
from heapq import heappop,heappush
import sys
input=sys.stdin.readline

q=int(input())
query=[list(map(int,input().split())) for _ in range(q)]
inf=10**12
left=[inf]
left_sum=0
right=[inf]
right_sum=0

cnt=0
b=0
for i in range(q):
    if query[i][0]==1:
        a=query[i][1]
        b+=query[i][2]
        if cnt==0:
            d=right[0]
            if a>d:
                heappush(left,-heappop(right))
                heappush(right,a)
                right_sum+=a-d
                left_sum-=d
            else:
                heappush(left,-a)
                left_sum-=a
            cnt=1
        else:
            c=-left[0]
            if a<c:
                heappush(right,-heappop(left))
                heappush(left,-a)
                right_sum+=c
                left_sum+=c-a
            else:
                heappush(right,a)
                right_sum+=a
            cnt=0
    else:
        x=-left[0]
        if cnt==0:
            print(x,b+right_sum+left_sum)
        else:
            print(x,b+x+right_sum+left_sum)

Solution (Python):
from heapq import heappop,heappush
import sys
input=sys.stdin.readline

q=int(input())
query=[list(map(int,input().split())) for _ in range(q)]
inf=10**12
left=[inf]
left_sum=0
right=[inf]
right_sum=0

cnt=0
b=0
for i in range(q):
    if query[i][0]==1:
        a=query[i][1]
        b+=query[i][2]
        if cnt==0:
            d=right[0]
            if a>d:
                heappush(left,-heappop(right))
                heappush(right,a)
                right_sum+=a-d
                left_sum-=d
            else:
                heappush(left,-a)
                left_sum-=a
            cnt=1
        else:
            c=-left[0]
            if a<c:
                heappush(right,-heappop(left))
                heappush(left,-a)
                right_sum+=c
                left_sum+=c-a
            else:
                heappush(right,a)
                right_sum+=a
            cnt=0
    else:
        x=-left[0]
        if cnt==0:
            print(x,b+right_sum+left_sum)
        else:
            print(x,b+x+right_sum+left_sum)

Solution (Python):
from heapq import heappop,heappush
q=int(input())
query=[list(map(int,input().split())) for _ in range(q)]
inf=10**12
left=[inf]
left_sum=0
right=[inf]
right_sum=0

cnt=0
b=0
for i in range(q):
    if query[i][0]==1:
        a=query[i][1]
        b+=query[i][2]
        if cnt==0:
            d=right[0]
            if a>d:
                heappush(left,-heappop(right))
                heappush(right,a)
                right_sum+=a-d
                left_sum-=d
            else:
                heappush(left,-a)
                left_sum-=a
            cnt=1
        else:
            c=-left[0]
            if a<c:
                heappush(right,-heappop(left))
                heappush(left,-a)
                right_sum+=c
                left_sum+=c-a
            else:
                heappush(right,a)
                right_sum+=a
            cnt=0
    else:
        x=-left[0]
        if cnt==0:
            print(x,b+right_sum+left_sum)
        else:
            print(x,b+x+right_sum+left_sum)

Solution (Python):

import sys
from heapq import heappush, heappop, heapify

N=input()

hq1=[]  
hq2=[]  
fx=0     
for _ in range(N):
    q=map(int, sys.stdin.readline().split()) 

    if q[0]==1:
        q_type=q[0]
        a=q[1]
        b=q[2]
        heappush(hq1,a*-1)
        heappush(hq2,a)
        if hq2[0]<hq1[0]*-1:
            hq1_max=heappop(hq1)*-1
            hq2_min=heappop(hq2)
            heappush(hq1,hq2_min*-1)
            heappush(hq2,hq1_max)
            fx+=abs(hq1_max-hq2_min)
        fx+=b
    elif q[0]==2:
        print hq1[0]*-1,fx

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 10**18

def A():
    a, b = LI()
    if a <= 5:
        print(0)
    elif 6 <= a <= 12:
        print(b // 2)
    else:
        print(b)
    return


def B():
    r, d, x = LI()
    for i in range(10):
        print(x * r - d)
        x = x * r - d
    return


def C():
    n, m = LI()
    imo = [0 for i in range(n+1)]
    for _ in range(m):
        l, r = LI_()
        imo[l] += 1
        imo[r + 1] -= 1
    for i in range(1,n):
        imo[i] += imo[i - 1]
    ans = 0
    
    for i in imo:
        if i == m:
            ans += 1
    print(ans)
    return


def D():
    n, m = LI()
    a = LI()
    bc = LIR(m)
    bc.sort(key=lambda x: x[1], reverse=True)
    a.sort()
    index = 0
    suma = 0
    for b, c in bc:
        if index + b >= n:
            if a[n - 1] <= c:
                suma += (n - index) * c
            else: 
                br = bisect_left(a, c)
                if br > index:
                    suma += (br - index) * c
                    index = br
                    break
                else:
                    break
            index = n
            break
        if a[index + b - 1] < c:
            suma += b * c
            index += b
        else:
            if a[index] < c:
                bl = bisect_left(a, c)
                suma += (bl - index) * c
                index = bl
            else:
                break
    suma += sum(a[index:])
    print(suma)

    return


def E():
    n, m, k = LI()
    def cmb(n, r, mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    g1 = [1, 1] 
    g2 = [1, 1]
    inverse = [0, 1] 

    for i in range( 2, n*m + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append((g2[-1] * inverse[-1]) % mod)
        
    ans = 0
    for d in range(1,n+1):
        ans += d*cmb(n * m - 2, k - 2, mod) * (n - d) * m ** 2 
    for d in range(1,m+1):
        ans += d*cmb(n * m - 2, k - 2, mod) * (m - d) * n ** 2
    print(ans%mod)
    

    
    return


def F():
    q = II()
    small = []
    big = []
    len_small = 0
    len_big = 0
    ans = 0
    for i in range(q):
        query = LI()

        if query[0] == 1:
            a, b = query[1:3]
            ans += b
            if len_small == 0:
                heappush(small, -a)
                len_small += 1
                continue
            if len_big == 0:
                num_small = -heappop(small)
                lis = [a, num_small]
                lis.sort()
                heappush(small, -lis[0])
                heappush(big, lis[1])
                len_big += 1
                if lis[0] == a:
                    ans += num_small - lis[0]
                else:
                    ans += (a - num_small)
                continue
            num_small = -heappop(small)
            num_big = heappop(big)
            lis = [a, num_big, num_small]
            lis.sort()
            if len_big != len_small:
                heappush(small, -lis[0])
                heappush(big, lis[1])
                heappush(big, lis[2])
                if lis[0] == a:
                    ans -= (num_small - a) * (len_small - 1)
                    ans += (num_small - a) * (len_big + 1)
                else:
                    ans += a - num_small
                len_big += 1
            else:
                heappush(small, -lis[0])
                heappush(small, -lis[1])
                heappush(big, lis[2])
                if lis[0] == a:
                    ans += num_small - a
                elif lis[1] == a:
                    ans += (a - num_small) * len_small
                    ans -= (a - num_small) * len_big
                else:
                    ans += (num_big - num_small) * len_small
                    ans -= (num_big - num_small) * len_big
                    ans += a - num_big
                len_small += 1

        else:
            a = -small[0]
            print(a, ans)
    return



if __name__ == '__main__':
    F()