Problem:


Score : 600 points

Problem Statement

There is a function f(x), which is initially a constant function f(x) = 0.

We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:

An update query 1 a b: Given two integers a and b, let g(x) = f(x) + |x - a| + b and replace f(x) with g(x).

An evaluation query 2: Print x that minimizes f(x), and the minimum value of f(x). If there are multiple such values of x, choose the minimum such value.

We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.

Constraints

All values in input are integers.

1 \leq Q \leq 2 \times 10^5

-10^9 \leq a, b \leq 10^9

The first query is an update query.

Input

Input is given from Standard Input in the following format:

Q
Query_1
:
Query_Q

See Sample Input 1 for an example.

Output

For each evaluation query, print a line containing the response, in the order in which the queries are given.

The response to each evaluation query should be the minimum value of x that minimizes f(x), and the minimum value of f(x), in this order, with space in between.

Sample Input 1

4
1 4 2
2
1 1 -8
2

Sample Output 1

4 2
1 -3

In the first evaluation query, f(x) = |x - 4| + 2, which attains the minimum value of 2 at x = 4.

In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6, which attains the minimum value of -3 when 1 \leq x \leq 4. Among the multiple values of x that minimize f(x), we ask you to print the minimum, that is, 1.

Sample Input 2

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

Sample Output 2

-1000000000 3000000000



Sample input:
4
1 4 2
2
1 1 -8
2


Sample output:
4 2
1 -3

Submission status: Accepted

Solution code:
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
        #print("rebuild:",self.id_size)
        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)

Submission status: Accepted

Solution code:
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
        #print("rebuild:",self.id_size)
        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)

Submission status: Accepted

Solution code:
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

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    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:n以上の最小の2のべき乗
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]

Submission status: Accepted

Solution code:
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
        #print("rebuild:",self.id_size)
        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
                else:
                    nd=nd.left
            else:
                if k==0:
                    return res_sum+((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
        mid=A.kth((n+1)//2-1)-10**9
        smallsum=A.kth_sum((n+1)//2-1)
        smallsum-=((n+1)//2)*10**9
        print(mid,S-2*smallsum+B+(n%2)*mid)

Submission status: Accepted

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

A_left, A_right = [], []
A_left_sum, A_right_sum = 0, 0
heapq.heapify(A_left)
heapq.heapify(A_right)

B_sum = 0
for _ in range(Q):
    query = list(map(int,input().split()))

    if query[0] == 1:#更新クエリ
        now = query[1]#a
        B_sum += query[2]#b

        l, r = len(A_left), len(A_right)
        #中央値がA_left[0]になるように、出し入れする。
        if l <= r:
            heapq.heappush(A_right, now)
            A_right_sum += now

            out = heapq.heappop(A_right)
            A_right_sum -= out

            heapq.heappush(A_left, -out)
            A_left_sum += out
        else:
            heapq.heappush(A_left, -now)
            A_left_sum += now

            out = -heapq.heappop(A_left)
            A_left_sum -= out

            heapq.heappush(A_right, out)
            A_right_sum += out
        #print(A_right, A_left, A_right_sum, A_left_sum)   
    else:#求値クエリ
        m = -A_left[0]
        #A_left は 全て m より小さいので、　m - xi の和は
        #m * len(A_left) - (xiの和）となる。
        #xiの和が、A_left_sumである。
        #A_right も同様だが。引く数の方が大きいため、正負が入れ替わることに注意
        ans = len(A_left) * m - A_left_sum - len(A_right) * m + A_right_sum + B_sum
        print(m, ans)

Submission status: Accepted

Solution code:
import heapq

q = int(input())
big, small = [], []
heapq.heapify(big)
heapq.heapify(small)
sumb = 0
sumdist = 0
i = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        i += 1
        a, b = query[1], query[2]
        sumb += b
        if i % 2 == 1:
            if i == 1:
                median = a
            else:
                if big[0] <= a:
                    median = heapq.heappushpop(big, a)
                    sumdist += abs(a - median)
                elif a <= -small[0]:
                    median = -heapq.heappushpop(small, -a)
                    sumdist += abs(a - median)
                else:
                    median = a
        else:
            sumdist += abs(a - median)
            heapq.heappush(big, max(a, median))
            heapq.heappush(small, -min(a, median))
            median = -small[0]
    else:
        print(median, sumdist + sumb)