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: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
前回の最小区間を覚えておいて，差分で最小値を更新する
"""

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################


    
    inf=10**9+1
    Q=I()
    ssl1 = SquareSkipList(square=2000)
    ssl1.add(-inf)
    ssl2 = SquareSkipList(square=2000)
    ssl2.add(inf)
    m=0#最小値
    
    s1=0#和
    s2=0
    
    q,a,b=MI()
    mx=a
    m=b
    
    
    for _ in range(Q-1):
        q=LI()
        if q[0]==1:
            a=q[1]
            m+=q[2]
            aa=ssl1.search_lower(inf)#下側の最大値
            bb=ssl2.search_higher(-inf)#上側の最小値
            l1=ssl1.len()
            l2=ssl2.len()
            
            if a<aa:
                ssl1.add(a)
                s1+=a
            elif a>bb:
                ssl2.add(a)
                s2+=a
            else:
                if a>mx:
                    a,mx=mx,a
                if l2<=l1:
                    ssl2.add(mx)
                    s2+=mx
                    aa=mx
                    mx=a
                else:
                    ssl1.add(a)
                    bb=a
                    s1+=a
                    
            if abs(l1-l2)>=2:
                if l1<l2:
                    ssl1.add(mx)
                    s1+=mx
                    ssl2.remove(bb)
                    s2-=bb
                    mx=bb
                else:
                    ssl2.add(mx)
                    s2+=mx
                    ssl1.remove(aa)
                    s1-=aa
                    mx=aa
        else:
            temp=m
            l1=ssl1.len() -1
            l2=ssl2.len() -1
            temp+=l1*mx-s1
            temp+=s2-l2*mx
            print(mx,temp)
                    
                
            
            
            
            
        
        
    

main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
前回の最小区間を覚えておいて，差分で最小値を更新する
"""

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################


    
    inf=10**9+1
    Q=I()
    ssl1 = SquareSkipList(square=2000)
    ssl1.add(-inf)
    ssl2 = SquareSkipList(square=2000)
    ssl2.add(inf)
    m=0#最小値
    
    s1=0#和
    s2=0
    
    q,a,b=MI()
    mx=a
    m=b
    
    
    for _ in range(Q-1):
        q=LI()
        if q[0]==1:
            a=q[1]
            m+=q[2]
            aa=ssl1.search_lower(inf)#下側の最大値
            bb=ssl2.search_higher(-inf)#下側の最大値
            l1=ssl1.len()
            l2=ssl2.len()
            
            if a<aa:
                ssl1.add(a)
                s1+=a
            elif a>bb:
                ssl2.add(a)
                s2+=a
            else:
                if a>mx:
                    a,mx=mx,a
                if l2<=l1:
                    ssl2.add(mx)
                    s2+=mx
                    aa=mx
                    mx=a
                else:
                    ssl1.add(a)
                    bb=a
                    s1+=a
                    
            if abs(l1-l2)>=2:
                if l1>l2:
                    ssl1.add(mx)
                    s1+=mx
                    ssl2.remove(aa)
                    s2-=aa
                    mx=aa
                else:
                    ssl2.add(mx)
                    s2+=mx
                    ssl1.remove(bb)
                    s1-=bb
                    mx=bb
        else:
            temp=m
            l1=ssl1.len() -1
            l2=ssl2.len() -1
            temp+=l1*mx-s1
            temp+=s2-l2*mx
            print(mx,temp)
                    
                
            
            
            
            
        
        
    

main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
前回の最小区間を覚えておいて，差分で最小値を更新する
"""

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################


    
    inf=10**9+1
    Q=I()
    ssl1 = SquareSkipList(square=1000)
    ssl1.add(-inf)
    ssl2 = SquareSkipList(square=1000)
    ssl2.add(inf)
    m=0#最小値
    
    s1=0#和
    s2=0
    
    q,a,b=MI()
    mx=a
    m=b
    
    
    for _ in range(Q-1):
        q=LI()
        if q[0]==1:
            a=q[1]
            m+=q[2]
            aa=ssl1.search_lower(inf)#下側の最大値
            bb=ssl2.search_higher(-inf)#下側の最大値
            l1=ssl1.len()
            l2=ssl2.len()
            
            if a<aa:
                ssl1.add(a)
                s1+=a
            elif a>bb:
                ssl2.add(a)
                s2+=a
            else:
                if a>mx:
                    a,mx=mx,a
                if l2<=l1:
                    ssl2.add(mx)
                    s2+=mx
                    aa=mx
                    mx=a
                else:
                    ssl1.add(a)
                    bb=a
                    s1+=a
                    
            if abs(l1-l2)>=2:
                if l1>l2:
                    ssl1.add(mx)
                    s1+=mx
                    ssl2.remove(aa)
                    s2-=aa
                    mx=aa
                else:
                    ssl2.add(mx)
                    s2+=mx
                    ssl1.remove(bb)
                    s1-=bb
                    mx=bb
        else:
            temp=m
            l1=ssl1.len()
            l2=ssl2.len()
            temp+=l1*mx-s1
            temp+=s2-l2*mx
            print(mx,temp)
                    
                
            
            
            
            
        
        
    

main()

Submission status: Runtime Error

Solution code:
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:
            if self.right:
                if -self.left[0] > n:
                    heappush(self.size_l, -n)
                    self.size_l += 1
                    self.sum_l += n
                else:
                    heappush(self.right, n)
                    self.size_r += 1
                    self.sum_r += n
            else:
                if -self.left[0] > n:
                    a = -heappop(self.left)
                    self.sum_l -= a
                    heappush(self.right, a)
                    self.sum_r += a
                    heappush(self.left, -n)
                    self.sum_l += n
                else:
                    heappush(self.right, n)
                    self.sum_r += n
                self.size_r += 1
        else:
            if self.left:
                if self.right and self.right[0] < n:
                    heappush(self.right, n)
                    self.size_r += 1
                    self.sum_r += n
                else:
                    heappush(self.left, -n)
                    self.size_l += 1
                    self.sum_l += n
            else:
                heappush(self.left, -n)
                self.size_l += 1
                self.sum_l += n
    
    def get(self):
        if self.size_l >= self.size_r:
            v = -heappop(self.left)
            heappush(self.left, -v)
        else:
            v = heappop(self.right)
            heappush(self.right, v)
        return v


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()

Submission status: Runtime Error

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

    #query_type->[1,1,2,1,2]
    #ab_list->[(a,b),(a,b),(a,b)]

    L=[]
    R=[]

    ini=0

    counter=0
    ab_pointer=0
    minF=0
    for i in query_type:
        if i==1:
            if counter==0:
                ini=ab_list[ab_pointer][0]
                counter+=1
                minF+=ab_list[ab_pointer][1]
            elif counter==1:
                L.append(-1*min(ini,ab_list[ab_pointer][0]))
                R.append(max(ini,ab_list[ab_pointer][0]))
                counter+=1
                delta=abs(-1*L[0]-R[0])
                minF+=delta+ab_list[ab_pointer][1]
            else:
                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:
            if counter<=1:
                print(str(ini)+" "+str(minF))
            else:
                print(str(-1*heappop(L))+" "+str(minF))



if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
Q = int(input())
query = []
sumL, sumR = [], []
ans = 0
for _ in range(Q):
    a = list(map(int, input().split()))
    if a[0]==1:
        ans += a[2]
        if len(sumL)==0 or a[1] <= -sumL[0]:
            heappush(sumL, -a[1])
            ans += -sumL[0] - a[1]
        else:
            heappush(sumR, a[1])
            ans += sumL[0] + a[1]
    
        if len(sumR) > len(sumL):
            ans -= sumR[0] + sumL[0]
            heapposh(sumL, -heappop(sumR))
            
        elif len(sumL) - len(sumR) >= 2:
            heappush(sumR, -heappop(sumL))

    else:
        print(-sumL[0],ans)

Submission status: Runtime Error

Solution code:
Q = int(input())
query = []
cal = []
intc = []
count = 0

for _ in range(Q):
    a = list(map(int, input().split()))
    if a[0]==1:
        intc.append(a[2])
        query.append(a[1])
        count += 1

    else:
        cal.append(count)


for c in cal:
    if c==1:
        print(query[0],intc[0])

    else:
        query = query[:c]
        query.sort()
        if c==2:
            print(query[0],sum(intc[:2])+query[1]-query[0])
        else:
            minx = int((c-1)/2)
            ans = -sum(query[:minx])+sum(query[minx+1:])+sum(intc[:c])
            print(query[minx],ans)

Submission status: Runtime Error

Solution code:
Q = int(input())
A = []
B = 0

for i in range(Q):
  query = list(map(int, input().split()))
  if query[0] == 1:
    A.append(query[1])
    B += query[2]
  if query[0] == 2:
    A.sort(inverse True)
    if len(A) % 2 == 0:
      min = A[len(A) // 2]

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
  return list(map(int,input().split()))
def m(): #複数文字
  return map(int,input().split())
def onem(): #Nとかの取得
  return int(input())
def s(x): #圧縮
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): #listをスペースごとに分ける
  return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
  return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
  ll = 0
  rr = r
  while True:
    mid = (ll+rr)//2

  if rr == mid:
    return ll
  if (ここに評価入れる):
    rr = mid
  else:
    ll = mid+1
"""

q = onem()

b = 0

AR = []
AL = []

ans = 0



for i in range(q):
  a = l()
  if len(a) == 1:
    if len(AR) == len(AL):
      print(min(AR[0]*-1,AL[0]),ans + b)
    else:
      print(AR[0]*-1,ans + b)

  else:
    b += a[2]
    if AR == []:
      AR.append(-a[1])
    else:
      if len(AR) == len(AL):
        if AL[0] < a[1]:
          ans += a[1]-AL[0]
          hq.heappush(AL,a[1])
          ppp = hq.heappop(AL)
          hq.heappush(AR,ppp*-1)
        else:
          ans += (-1*AR[0] - a[1])
          hq.heappush(AR,a[1]*-1)

      else:
        if (AR[0]* -1) > a[1]:
          ans += (-1*AR[0] - a[1])
          hq.heappush(AR,a[1]*-1)
          ppp = hq.heappop(AR)*-1
          hq.heappush(AL,ppp)
        else:
          ans += (-AL[0] + a[1])
          hq.heappush(AL,a[1])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
	int Q;cin >>Q;
	ll a,b,q;
	ll su=0,ans=0;
	pair<ll,ll> cn=make_pair(10000000000,0); //firstは数字、secondは個数
	map<ll,ll> cnt;
	vector<ll> A;
	for (int i=0;i<Q;i++)
	{
		cin >>q;
		if (q==1)
		{
			cin >> a >>b;
			su+=b;
			A.push_back(a);
			cnt[a]+=1;
			if (cnt[a]>=cn.second)
			{
				if (a<cn.first)
				{
					cn.first=a;
					cn.second=cnt[a];
				}
			}
		}
		else
		{
			ans=0;
			for (int i=0;i<A.size();i++)
			{
				ans+=abs(cn.first-A[i]);
			}
			ans+=su;
			cout << cn.first<<" "<< ans<< endl;
		}
	}
	return 0;
}

Submission status: Runtime Error

Solution code:
import heapq

Q = int(input())
m = L = R = 0
l, r = [], []
n = 0
b = 0

for i in range(Q):
  query = list(map(int, input().split()))
  if len(query) == 3: # 更新クエリ
    b += query[2]
    new = query[1]
    if  n == 0:
      m = new
    elif n == 1:
      if new <= m:
        heapq.heappush(l, -new)
        heapq.heappush(r, m)
        L, R = new, m
        m = new
      else:
        heapq.heappush(l, -m)
        heapq.heappush(r, new)
        L, R = m, new
    elif n == 2:
      if new < m:
        m = -heapq.heappop(l)
        heapq.heappush(l, -new)
        L = new
      else:
        _r = heapq.heappop(r)
        if new < _r:
          m = new
          heapq.heappush(r, _r)
        else:
          m = _r
          heapq.heappush(r, new)
          R = new
    else:
      _l = - heapq.heappop(l)
      _r = heapq.heappop(r)
      if n%2:
        if new <= _l:
          heapq.heappush(l, -new)
          heapq.heappush(r, _r)
          heapq.heappush(r, m)
          m, L, R = l, L+new, R+m
        elif new <= m:
          heapq.heappush(l, -_l)
          heapq.heappush(r, _r)
          heapq.heappush(r, m)
          m, L, R = new, L+new, R+m
        else:
          heapq.heappush(l, -_l)
          heapq.heappush(r, _r)
          heapq.heappush(r, new)
          L, R = L+m, R+new
      else:
        if new <= m:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -new)
          heapq.heappush(r, _r)
          L += new - m
        elif new <= _r:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -m)
          heapq.heappush(r, _r)
          m = new
        else:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -m)
          heapq.heappush(r, new)
          m, R = _r, R+new-_r
    n += 1
  else: # 求値クエリ
    print(m, R-L+b)