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 Medians:
    def __init__(self):
        self.left = []
        self.right = []
        self.size_l = 0
        self.size_r = 0
        self.sum_l = 0
        self.sum_r = 0

    def add(self, n):
        if self.size_l > self.size_r:
            t = -self.left[0]
            if n >= t:
                heappush(self.right, n)
                self.sum_r += n
            else:
                heappop(self.left)
                self.sum_l -= t
                heappush(self.left, -n)
                self.sum_l += n
                heappush(self.right, t)
                self.sum_r += t
            self.size_r += 1
        else:
            if not self.size_l:
                heappush(self.left, -n)
                self.sum_l += n
            else:
                t = self.right[0]
                if n <= t:
                    heappush(self.left, -n)
                    self.sum_l += n
                else:
                    heappop(self.right)
                    self.sum_r -= t
                    heappush(self.right, n)
                    self.sum_r += n
                    heappush(self.left, -t)
                    self.sum_l += t
            self.size_l += 1
    
    def get(self):
        return -self.left[0]


def solve():
    Q = int(input())
    s = 0
    med = Medians()
    for _ in range(Q):
        q, *l, = map(int, input().split())
        if q == 1:
            a, b = l
            s += b
            med.add(a)
        else:
            m = med.get()
            d1 = med.size_l - med.size_r
            d2 = med.sum_r - med.sum_l
            print(m, m*d1+d2+s)


if __name__ == "__main__":
    solve()

Solution (Python):
from heapq import heappop, heappush


class Medians:
    def __init__(self):
        self.left = []
        self.right = []
        self.size_l = 0
        self.size_r = 0
        self.sum_l = 0
        self.sum_r = 0

    def add(self, n):
        if self.size_l > self.size_r:
            t = -self.left[0]
            if n >= t:
                heappush(self.right, n)
                self.sum_r += n
            else:
                heappop(self.left)
                self.sum_l -= t
                heappush(self.left, -n)
                self.sum_l += n
                heappush(self.right, t)
                self.sum_r += t
            self.size_r += 1
        else:
            if not self.size_l:
                heappush(self.left, -n)
                self.sum_l += n
            else:
                t = self.right[0]
                if n <= t:
                    heappush(self.left, -n)
                    self.sum_l += n
                else:
                    heappop(self.right)
                    self.sum_r -= t
                    heappush(self.right, n)
                    self.sum_r += n
                    heappush(self.left, -t)
                    self.sum_l += t
            self.size_l += 1
    
    def get(self):
        return -self.left[0]


def solve():
    Q = int(input())
    s = 0
    med = Medians()
    for _ in range(Q):
        q, *l, = map(int, input().split())
        if q == 1:
            a, b = l
            s += b
            med.add(a)
        else:
            m = med.get()
            d1 = med.size_l - med.size_r
            d2 = med.sum_r - med.sum_l
            print(m, m*d1+d2+s)


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    Q = int(input())
    
    
    
    
    low=[]
    high=[]
    s1=s2=0
    btot=0
    for _ in range(Q):
        q=list(map(int, input().split()))
        if q[0]==1:
            a,b=q[1:]
            btot+=b
            if not low:
                heappush(low,-a)
                s1+=a
                continue
            if a>-low[0]:
                heappush(high,a)
                s2+=a
                if len(low)<len(high):
                    a2=heappop(high)
                    heappush(low,-a2)
                    s2-=a2
                    s1+=a2
            else:
                heappush(low,-a)
                s1+=a
                if len(high)+1<len(low):
                    a2=-heappop(low)
                    heappush(high,a2)
                    s1-=a2
                    s2+=a2
        else:
            if len(low)==0:
                print(0)
                continue
            ans=btot
            mid=-low[0]
            ans+=len(low)*mid-s1-len(high)*mid+s2
            print(mid,round(ans))

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
qq = int(input())
ans = 0
hq1 = []
hq2 = []
x = 10 ** 10
c = 0
p, q = 0, 0
for _ in range(qq):
    que = list(map(int, input().split()))
    if que[0] == 1:
        a, b = que[1:]
        ans += b
        if c % 2 == 0:
            if a <= x:
                heapq.heappush(hq1, -a)
                p += a
            else:
                heapq.heappush(hq2, a)
                q += a
                y = heapq.heappop(hq2)
                q -= y
                heapq.heappush(hq1, -y)
                p += y
        else:
            if a <= x:
                heapq.heappush(hq1, -a)
                p += a
                y = -heapq.heappop(hq1)
                p -= y
                heapq.heappush(hq2, y)
                q += y
            else:
                heapq.heappush(hq2, a)
                q += a
        x = -hq1[0]
        c += 1
    else:
        print(x, q - len(hq2) * x + len(hq1) * x - p + ans)

Solution (Python):

import heapq
Q = int(input())
que = [tuple(map(int, input().split())) for _ in range(Q)]

const_term = 0
smaller = []  
smaller_sum = 0
bigger = []  
bigger_sum = 0
heapq.heapify(smaller)
heapq.heapify(bigger)
add_count = 0  
for x in que:
    status = x[0]
    if status == 1:
        
        add_value, add_const = x[1], x[2]
        const_term += add_const
        if add_count == 0:
            heapq.heappush(smaller, -add_value)
            smaller_sum += add_value
            add_count += 1
            continue
        elif add_count % 2 == 0:
            k_term = smaller[0]*(-1)
            k_1_term = bigger[0]
            if k_1_term >= add_value:
                heapq.heappush(smaller, add_value*(-1))
                smaller_sum += add_value
                add_count += 1
                continue
            elif k_1_term < add_value:
                x = heapq.heappop(bigger)
                bigger_sum -= x
                heapq.heappush(smaller, -x)
                smaller_sum += x
                heapq.heappush(bigger, add_value)
                bigger_sum += add_value
                add_count += 1
                continue
        else:
            if add_count == 1:
                k_term = smaller[0]*(-1)
                add_count += 1
                if k_term <= add_value:
                    heapq.heappush(bigger, add_value)
                    bigger_sum += add_value
                    continue
                elif k_term > add_value:
                    x = heapq.heappop(smaller)*(-1)
                    smaller_sum -= x
                    heapq.heappush(bigger, x)
                    bigger_sum += x
                    heapq.heappush(smaller, -add_value)
                    smaller_sum += add_value
                    continue
            else:
                add_count += 1
                k_1_term = heapq.heappop(smaller)*(-1)
                smaller_sum -= k_1_term
                M = max(k_1_term, add_value)
                m = min(k_1_term, add_value)
                heapq.heappush(bigger, M)
                bigger_sum += M
                heapq.heappush(smaller, -m)
                smaller_sum += m
                continue

    else:
        
        X = smaller[0]*(-1)
        P = (add_count+1)//2
        print(X, bigger_sum-smaller_sum+X*(2*P-add_count)+const_term)

Solution (Python):

import sys
from heapq import heappush, heappop, heapify

INF = float("inf")


def main():
    Q = int(input())
    bottom = [INF]                 
    top = [INF]               
    bottom_total = 0
    top_total = 0

    btot = 0
    for i in range(Q):
        q = input()
        if q[0] == "1":
            _, a, b = map(int, q.split())
            
            btot += b
            if top[0] < a:
                
                heappush(top, a)
                top_total += a
            elif -bottom[0] < a:
                
                heappush(bottom, -a)
                bottom_total += a
            else:
                
                heappush(bottom, -a)
                bottom_total += a

            
            
            while len(top) - len(bottom) > 0:
                heappush(bottom, -top[0])
                bottom_total += top[0]
                top_total -= heappop(top)
            
            while len(bottom)-len(top) > 1:
                heappush(top, -bottom[0])
                top_total += -bottom[0]
                bottom_total -= -heappop(bottom)
        else:
            tot = btot
            tot += (len(bottom)*(-bottom[0]) - bottom_total)
            tot += (top_total - len(top)*(-bottom[0]))
            print(-bottom[0], tot)
        
    

    return


if __name__ == '__main__':
    main()

Solution (Python):
q=int(input())
a=0
b=0
g,l,ans=map(int,input().split())
r=l
now=1
from heapq import heappop, heappush
le,ri=[],[]
for i in range(q-1):
    cin=tuple(map(int,input().split()))
    if cin[0]==2:
        print(l,ans)
    else:
        x=cin[1]
        ans+=cin[2]
        if not(l<=x<=r):
            ans+=min(abs(x-l),abs(r-x))
        now+=1
        if now%2:
            heappush(le,-min(l,r,x))
            heappush(ri,max(l,r,x))
            l=l+r+x-max(l,r,x)-min(l,r,x)
            r=l
        else:
            if l<=x:
                heappush(ri,x)
                r=heappop(ri)
            else:
                heappush(le,-x)
                l,r=-heappop(le),l

Solution (Python):
import heapq

q = int(input())
ans = []
mini = 0
left, right = [], []
cnt = 0
mid = None
for _ in range(q):
    qi = input()
    if qi == '2':
        if cnt%2 == 0:
            ans.append([-left[0], mini])
        else:
            ans.append([mid, mini])
    else:
        kind, a, b = map(int, qi.split())
        if cnt%2 == 1:
            mini += abs(mid-a) + b
            heapq.heappush(left, -min(mid, a))
            heapq.heappush(right, max(mid, a))
            mid = None
        else:
            if cnt == 0:
                mid = a
                mini = b
                cnt += 1
                continue
            l = -heapq.heappop(left)
            r = heapq.heappop(right)
            if a <= l:
                mini += l-a + b
                heapq.heappush(left, -a)
                heapq.heappush(right, r)
                mid = l
            elif a <= r:
                mini += b
                heapq.heappush(left, -l)
                heapq.heappush(right, r)
                mid = a
            else:
                mini += a-r + b
                heapq.heappush(left, -l)
                heapq.heappush(right, a)
                mid = r
        cnt += 1

for i, j in ans:
    print(i, j)

Solution (Python):
import heapq

q = int(input())
ans = []
mini = 0
left, right = [], []
cnt = 0
mid = None
for _ in range(q):
    qi = input()
    if qi == '2':
        if cnt%2 == 0:
            ans.append([-left[0], mini])
        else:
            ans.append([mid, mini])
    else:
        kind, a, b = map(int, qi.split())
        if cnt%2 == 1:
            mini += abs(mid-a) + b
            heapq.heappush(left, -min(mid, a))
            heapq.heappush(right, max(mid, a))
            mid = None
        else:
            if cnt == 0:
                mid = a
                mini = b
                cnt += 1
                continue
            l = -heapq.heappop(left)
            r = heapq.heappop(right)
            if a <= l:
                mini += l-a + b
                heapq.heappush(left, -a)
                heapq.heappush(right, r)
                mid = l
            elif a <= r:
                mini += b
                heapq.heappush(left, -l)
                heapq.heappush(right, r)
                mid = a
            else:
                mini += a-r + b
                heapq.heappush(left, -l)
                heapq.heappush(right, a)
                mid = r
        cnt += 1

for i, j in ans:
    print(i, j)

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

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

        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=1):
            
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            
            
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i

        def debug(self, k):
            return [self.sum(i) for i in range(k)]
    def compress(list1):
        list2 = sorted(set(list1))
        memo = {value: index for index, value in enumerate(list2)}
        for i in range(len(list1)):
            list1[i] = memo[list1[i]]
        return memo, len(list2)
    n = I()
    Q = [LI()for _ in range(n)]
    A = []
    for q in Q:
        if q[0]==2:
            continue
        a, b = q[1:]
        A.append(a)
    memo,N = compress(A)
    
    
    bit = Bit(N+1)
    bit_a = Bit(N+1)
    location = defaultdict(int)
    num = 0
    B = 0
    ans = []
    for q in Q:
        if q[0]==2:
            x = bit.search((num+1)//2)
            
            l = location[x]
            rep = l*bit.sum(x)-bit_a.sum(x)+B
            rep += bit_a.sum(N) - bit_a.sum(x) - l*(bit.sum(N) - bit.sum(x))
            ans.append((location[x],rep))
            continue
        a, b = q[1:]
        B += b
        bit.add(memo[a])
        bit_a.add(memo[a],a)
        location[memo[a]] = a
        num += 1

    for v in ans:
        print(" ".join(map(str,v)))
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
from heapq import*
L,R=[],[]
B=t=0
Q,*E=open(0)
for e in E:
  if' 'in e:_,a,b=map(int,e.split());t^=1;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)

Solution (Python):
from heapq import*
L,R=[],[]
B=t=0
Q,*E=open(0)
for e in E:
	if' 'in e:_,a,b=map(int,e.split());t^=1;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)

Solution (Python):
from heapq import*
L,R=[],[]
B=t=0
Q,*E=open(0)
for e in E:
  if' 'in e:_,a,b=map(int,e.split());t^=1;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)

Solution (Python):
from heapq import*;L,R=[],[];B=t=0;Q,*E=open(0)
for e in E:
  if' 'in e:_,a,b=map(int,e.split());t^=1;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)

Solution (Python):
import sys
input=sys.stdin.buffer.readline
q=int(input())
from heapq import heapify, heappop, heappush
L=[]
R=[]
s=0
ans=0
c=0
l,r=-10**10,10**10
for i in range(q):
    j=tuple(map(int ,input().split()))
    if j[0]==1:
        x,y=j[1],j[2]
        s+=1
        ans+=y
        if not(l<=x<=r):ans+=min(abs(l-x),abs(r-x))
        if s==1:
            heappush(L,-x)
            l,r=x,x
        elif s%2:
            if -L[0]>=x:
                heappush(L,-x)
                l,r=-L[0],-L[0]
            else:
                heappush(R,x)
                l=heappop(R)
                r=l
                heappush(L,-l)
        else:
            if -L[0]<=x:
                heappush(R,x)
            else:
                heappush(L,-x)
                heappush(R,-heappop(L))    
            l,r=-L[0],R[0]
    else:
        print(l,ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def main():
    Q = int(input())
    total_b = 0
    total_a = 0
    less_than_middle = 0
    left = []
    right = []
    cnt = 0
    for _ in range(Q):
        query = tuple(map(int,input().split()))
        if query[0] == 1:
            a,b = query[1:]
            total_b += b
            total_a += a
            cnt += 1
            heappush(right,a)
            while left and right and (-left[0] > right[0]):
                p = -heappop(left)
                q = heappop(right)
                heappush(left,-q)
                heappush(right,p)
                less_than_middle += -p + q
            if cnt%2 == 0:
                p = heappop(right)
                heappush(left,-p)
                less_than_middle += p
        else:
            if cnt%2 == 0:
                x = -left[0]
                ans = total_a - 2*less_than_middle + total_b
                print(x,ans)
            else:
                x = right[0]
                ans = total_a - 2*less_than_middle - x + total_b
                print(x,ans)
if __name__ == '__main__':
    main()

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

from heapq import heappush, heappop

q = int(input())
left = []
right = []
bias = 0
sum_left = 0
sum_right = 0

for _ in range(q):
    query = input().split()
    if len(query) == 3:
        n, a, b = [int(x) for x in query]
        bias += b
        if not right:
            if not left:
                heappush(left, -a)
                sum_left += a
            else:
                l = -heappop(left)
                if l > a:
                    heappush(left, -a)
                    heappush(right, l)
                    sum_right += l
                    sum_left += (a - l)
                else:
                    heappush(left, -l)
                    heappush(right, a)
                    sum_right += a
            continue
        l, r = -heappop(left), heappop(right)
        if len(left) == len(right):
            if a > r:
                heappush(right, a)
                heappush(left, -l)
                heappush(left, -r)
                sum_left += r
                sum_right += (a - r)
            else:
                heappush(left, -l)
                heappush(left, -a)
                heappush(right, r)
                sum_left += a
        else:
            if a < l:
                heappush(right, r)
                heappush(right, l)
                heappush(left, -a)
                sum_left += (a - l)
                sum_right += l
            else:
                heappush(right, r)
                heappush(right, a)
                heappush(left, -l)
                sum_right += a
    else:
        median = -heappop(left)
        print(median, -sum_left + sum_right + (-len(right) + len(left) + 1)*(median) + bias)
        heappush(left, -median)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(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
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1
  
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return memo, len(list2)

q = int(readline())
L = [list(map(int,readline().split())) for i in range(q)]
 

chk = []
for i in range(q):
    if L[i][0] == 1:
        chk.append(L[i][1])
        
memo, len_memo = compress(chk)
memo_inv = dict([(v,k) for k,v in memo.items()])


bit = Bit(len_memo)

num = Bit(len_memo)
  
s = 0
cnt = 0
for i in range(q):
  que = L[i]
  if que[0] == 1:
    a,b,c = que
    s += c
    cnt += 1
    bit.add(memo[b]+1,b)
    num.add(memo[b]+1,1)
  else:
    d = num.lower_bound((cnt+1)//2)
    m = memo_inv[d-1]
    sum1 = bit.sum(d)
    num1 = num.sum(d)
    sum2 = bit.sum(len_memo)-bit.sum(d)
    num2 = num.sum(len_memo)-num.sum(d)
    print(m,abs(num1*m-sum1)+abs(num2*m-sum2)+s)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class BinaryIndexedTree:
    
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    
    def add(self, i, x):
        
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def sum(self, i):
        
        res = 0
        while i:
            res += self.data[i]
            i -= i & -i
        return res
    
    def bisect_left(self, w):
        if w <= 0:
            return 0
        i = 0
        k = 1 << (self.n.bit_length() - 1)
        while 0 < k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k >>= 1
        return i + 1


def solve():
    Q = int(rl())
    queries = [tuple(map(int, rl().split())) for _ in range(Q)]
    
    a = []
    for query in queries:
        if query[0] == 1:
            a.append(query[1])
    sorted_a = sorted(set(a))
    a_to_idx = {val: idx for idx, val in enumerate(sorted_a)}
    idx_to_a = {val: key for key, val in a_to_idx.items()}
    
    N = len(sorted_a)
    bit0 = BinaryIndexedTree(N)
    bit1 = BinaryIndexedTree(N)
    
    b_sm = 0
    cnt = 0
    for query in queries:
        if query[0] == 1:
            _, a, b = query
            bit0.add(a_to_idx[a], a)
            bit1.add(a_to_idx[a], 1)
            b_sm += b
            cnt += 1
        else:
            med_x = idx_to_a[bit1.bisect_left((cnt + 1) // 2) - 1]
            under_sm = bit0.sum(a_to_idx[med_x])
            under_n = bit1.sum(a_to_idx[med_x])
            over_sm = bit0.sum(N) - under_sm
            over_n = bit1.sum(N) - under_n
            print(med_x, abs(under_n * med_x - under_sm) + abs(over_n * med_x - over_sm) + b_sm)


if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    q = int(input())
    b = 0
    hq_l, hq_r = [], []
    sum_l, sum_r = 0, 0

    for _ in range(q):
        a = list(map(int, input().split()))
        if a[0] == 1:
            b += a[2]
            if len(hq_l)==0 or a[1] <= -hq_l[0]:
                heappush(hq_l, -a[1])
                sum_l += a[1]
            else:
                heappush(hq_r, a[1])
                sum_r += a[1]
        else:
            while len(hq_l)-1 > len(hq_r):
                sum_l -= -hq_l[0]
                sum_r += -hq_l[0]
                m = -heappop(hq_l)
                heappush(hq_r, m)
            while len(hq_l) < len(hq_r):
                sum_l += hq_r[0]
                sum_r -= hq_r[0]
                m = -heappop(hq_r)
                heappush(hq_l, m)
            print(-hq_l[0],  (-hq_l[0]*len(hq_l)) - sum_l + sum_r - (-hq_l[0]*len(hq_r)) + b)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
q = int(input())
l = []
r = []
ai = 0
bs = 0
for i in range(q):
    ipt = list(map(int,input().split()))
    if ipt[0] == 1:
        al = heapq.heappushpop(l,-ipt[1])
        ar = heapq.heappushpop(r,ipt[1])
        ai -= (al+ar)
        heapq.heappush(l,-ar)
        heapq.heappush(r,-al)
        bs += ipt[2]
    else:
        an = heapq.heappop(l)
        print(-an,bs+ai)
        heapq.heappush(l,an)

Solution (Python):
from heapq import heappush,heappop
def main():
    Q=int(input())

    ab_list=[]
    query_type=[]

    for i in range(Q):
        query=list(map(int,input().split()))
        query_type.append(query[0])
        if query[0]==1:
            ab_list.append((query[1],query[2]))

    
    

    L=[]
    R=[]

    ini=0

    counter=0
    ab_pointer=0
    minF=0
    for i in query_type:
        if i==1:
            a_new=ab_list[ab_pointer][0]
            b_new=ab_list[ab_pointer][1]
            heappush(L,-1*a_new)
            heappush(R,a_new)
            Lmax=-1*heappop(L)
            Rmin=heappop(R)
            if Lmax<=Rmin:
                heappush(L,-1*Lmax)
                heappush(R,Rmin)
            else:
                heappush(L,-1*Rmin)
                heappush(R,Lmax)
            delta=abs(Lmax-Rmin)
            minF+=delta+b_new
            ab_pointer+=1
        else:
            minX=-1*heappop(L)
            print(str(minX)+" "+str(minF))
            heappush(L,-1*minX)



if __name__=="__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from bisect import insort

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

q = int(readline())
info = [list(map(int, input().split())) for i in range(q)]
 

li1 = []
for i in range(q):
    if info[i][0] == 1:
        li1.append(info[i][1])
        
memo, len_memo = compress(li1)

def median():
    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]
  

bit = BIT(len_memo)

bit1 = BIT(len_memo)
memo_inv = dict([(v,k) for k,v in memo.items()])
  
s = 0
cnt = 0
for i in range(q):
  que = info[i]
  if que[0] == 1:
    a,b,c = que
    s += c
    cnt += 1
    bit.add(memo[b],b)
    bit1.add(memo[b], 1)
  else:
    d = median()
    sum1 = bit.get(0, memo[d])
    num1 = bit1.get(0, memo[d])
    sum2 = bit.get(memo[d], len_memo)
    num2 = bit1.get(memo[d], len_memo)
    print(d, abs(num1*d- sum1) + abs(num2*d - sum2) + s)