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:
import heapq
const = 0
left = []
right = []

q = int(input())
cnt = 0
left_sum = 0
right_sum = 0
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        # update
        a, b = t[1:]
        const += b
        if cnt % 2 == 0:
            if not right:
                heapq.heappush(left, -a)
                left_sum += a
                cnt += 1
                #print(left_sum, right_sum, cnt)
                continue

            c = heapq.heappop(right)
            right_sum -= c
            if a <= c:
                heapq.heappush(left, -a)
                heapq.heappush(right, c)
                left_sum += a
                right_sum += c
            else:
                heapq.heappush(left, -c)
                heapq.heappush(right, a)
                left_sum += c
                right_sum += a
        else:
            c = heapq.heappop(left)
            left_sum += c
            if a <= -c:
                heapq.heappush(left, -a)
                heapq.heappush(right, -c)
                left_sum += a
                right_sum -= c
            else:
                heapq.heappush(left, c)
                heapq.heappush(right, a)
                left_sum -= c
                right_sum += a
        cnt += 1
        #print(left_sum, right_sum, cnt)
    else:
        tmp = -left[0]
        print(tmp, const - left_sum + right_sum + tmp * (cnt % 2))

Submission status: Accepted

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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    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 print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i+1) - B.sum(i))
    print(*ANS)


l = 10000
ll = 100
q = int(input())
Q = [list(map(int,input().split())) for i in range(q)]

from random import randint
# q = 20
# Q = []
# for i in range(q//2):
#     Q.append([1, randint(-ll,ll), randint(-ll,ll)])
#     Q.append([2])
# Q = [[1, 6, -10], [2], [1, -7, -3], [2], [1, 1, 6], [2], [1, 6, 10], [2], [1, -6, 9], [2]]
# print(Q)

A = []
for i in range(q):
    if Q[i][0] == 1:
        A.append((Q[i][1], i))
A.sort()
D = {}
for i in range(len(A)):
    D[A[i]] = i+1

B = Bit(len(D) + 2)
# print(D)
# print("A",A)

asum = 0
bsum = Q[0][2]
m_ind = D[(Q[0][1], 0)]
B.add(D[(Q[0][1], 0)], 1)
ok_a = 1
for i in range(1, q):
    if Q[i][0] == 2:
        # print("m_ind",m_ind)
        print(A[m_ind-1][0], asum+bsum)
    else:
        bsum += Q[i][2]
        B.add(D[(Q[i][1], i)], 1)
        # print_bit(B)
        if ok_a % 2 == 0 and D[(Q[i][1], i)] > m_ind:
            ng = 0
            ok = len(D)+2
            m = (ok+ng) // 2
            while abs(ok-ng) > 1:
                if B.sum(m) >= ok_a//2 + 1:
                    ok = m
                else:
                    ng = m
                m = (ok+ng) // 2
            m_ind = ok
        elif ok_a % 2 == 1 and D[(Q[i][1], i)] < m_ind:
            ng = 0
            # print("ok_a", ok_a)
            
            ok = len(D)+2
            m = (ok+ng) // 2
            while abs(ok-ng) > 1:
                if B.sum(m) >= ok_a//2 + 1:
                    ok = m
                else:
                    ng = m
                m = (ok+ng) // 2
            # print(ok,m_ind)
            asum += abs(A[ok-1][0]-A[m_ind-1][0])
            m_ind = ok
            
        asum += abs(Q[i][1]-A[m_ind-1][0])
        ok_a += 1


# A1 = []
# b1 = 0
# for i in range(q):
#     if Q[i][0] == 1:
#         A1.append(Q[i][1])
#         b1 += Q[i][2]
#     else:
#         ans = float("inf")
#         ansind = 0
#         for i in range(-l, l+1):
#             ans0 = b1
#             for j in range(len(A1)):
#                 ans0 += abs(A1[j]-i)
#             if ans0 < ans:
#                 ansind = i
#                 ans = ans0
#         print(ansind, ans)

Submission status: Accepted

Solution code:
import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

q = int(input())

import heapq
L = []
R = []
heapq.heapify(L)
heapq.heapify(R)

B = 0

for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        a, b = query[1], query[2]
        B += b
        heapq.heappush(L, -a)
        heapq.heappush(R, a)
        if -L[0] > R[0]:
            l = -heapq.heappop(L)
            r = heapq.heappop(R)
            B += l-r
            heapq.heappush(L, -r)
            heapq.heappush(R, l)
    else:
        print(-L[0], B)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
Q = I()
data = ILL(Q)

As = {-10**10,10**10}
for temp in data:
  if len(temp) == 3:
    As.add(temp[1])
    
As = list(As)
As.sort()

dic = DD(int)
for i in range(len(As)):
  dic[As[i]] = i 
  
class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

class BIT_RSQ_RAQ:
  def __init__(self, N):
    self.N = N
    self.data0 = [0]*(self.N+1)
    self.data1 = [0]*(self.N+1)
  def _add(self, data, k, x):
    while k <= self.N:
      data[k] += x
      k += k & -k
  def add(self, l, r, x):
    self._add(self.data0, l, -x*(l-1))
    self._add(self.data0, r, x*(r-1))
    self._add(self.data1, l, x)
    self._add(self.data1, r, -x)
  def _get(self, data, k):
    s = 0
    while k:
      s += data[k]
      k -= k & -k
    return s
  def query(self, l, r):
    return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

N = len(As)
B = BIT(int_log(N,2)+1)
ACC1 = BIT_RSQ_RAQ(N)
ACC2 = BIT_RSQ_RAQ(N)

base = 0
count = 0
for temp in data:
  if len(temp) == 3:
    _,a,b = temp
    ACC1.add(1,dic[a]+1,a+10**10)
    ACC2.add(dic[a]+2,N+1,10**10-a)
    base += b
    count += 1
    B.add(dic[a],1)
  else:
    x = As[B.bisect((count+1)//2)]
    #print(x,ACC1.query(dic[x]+1,dic[x]+2),(x+10**10),(count-B.sum(dic[x])),ACC2.query(dic[x]+1,dic[x]+2),(10**10-x),(B.sum(dic[x]-1)),base)
    print(x,ACC1.query(dic[x]+1,dic[x]+2)-(x+10**10)*(count-B.sum(dic[x]))+ACC2.query(dic[x]+1,dic[x]+2)-(10**10-x)*(B.sum(dic[x]-1))+base)

Submission status: Accepted

Solution code:
q=int(input())
query=[input() for _ in range(q)]
from bisect import bisect_left
ary=[-float('inf')]
for qq in query:
  if qq[0]=='1':
    _,a,_=map(int,qq.split())
    ary.append(a)
ary.sort()
ary.append(float('inf'))

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
        return self.el[i]
    return self.sum(j) - self.sum(i)

ml,mr=0,len(ary)+1
mv=0
bit=BIT(len(ary)+1)
for qq in query:
  if qq[0]=='2':
    print(ary[ml],mv)
  else:
    _,a,b=map(int,qq.split())
    a=bisect_left(ary,a)
    bit.add(1,-1)
    bit.add(a+1,2)
    if ml<=a<mr:
      mv+=b
      ml,mr=a,a+1
    else:
      l,r=1,len(ary)+2
      # はじめて0以上になる場所を二分探索→ここがml
      while r-l>1:
        x=(r+l)//2
        if bit.sum(x)>=0:
          l,r=l,x
        else:
          l,r=x,r
      # はじめて1以上になる場所を二分探索→ここがmr
      mv+=b
      mv+=min(abs(ary[l]-ary[ml]),abs(ary[l]-ary[mr]))+abs(ary[l]-ary[a])
      ml=l
      l,r=1,len(ary)+2
      while r-l>1:
        x=(r+l)//2
        if bit.sum(x)>0:
          l,r=l,x
        else:
          l,r=x,r
      mr=l

Submission status: Accepted

Solution code:
q=int(input())
query=[input() for _ in range(q)]
from bisect import bisect_left
ary=[-float('inf')]
for qq in query:
  if qq[0]=='1':
    _,a,_=map(int,qq.split())
    ary.append(a)
ary.sort()
ary.append(float('inf'))

class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  # 区間[l,r)へのクエリ
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)

ml,mr=0,len(ary)+1
mv=0
st=SegmentTree(len(ary))
for qq in query:
  if qq[0]=='2':
    print(ary[ml],mv)
  else:
    _,a,b=map(int,qq.split())
    a=bisect_left(ary,a)
    st.add(0,-1)
    st.add(a,2)
    if ml<=a<mr:
      mv+=b
      ml,mr=a,a+1
    else:
      l,r=0,len(ary)+1
      # はじめて0以上になる場所を二分探索→ここがml
      while r-l>1:
        x=(r+l)//2
        if st.query(0,x)>=0:
          l,r=l,x
        else:
          l,r=x,r
      # はじめて1以上になる場所を二分探索→ここがmr
      mv+=b
      mv+=min(abs(ary[l]-ary[ml]),abs(ary[l]-ary[mr]))+abs(ary[l]-ary[a])
      ml=l
      l,r=0,len(ary)+1
      while r-l>1:
        x=(r+l)//2
        if st.query(0,x)>0:
          l,r=l,x
        else:
          l,r=x,r
      mr=l

Submission status: Accepted

Solution code:
from bisect import bisect_left
q=int(input())
query=[input() for _ in range(q)]
l,r=-pow(10,9),pow(10,9)
ary=[-float('inf')]
for qq in query:
    if qq[0]=='1':
        _,a,b=map(int,qq.split())
        ary.append(a)
ary.append(float('inf'))
ary.sort()

class SegmentTree():
    def __init__(self,size,segfunc=lambda x,y:x+y,default=0):
        self.segfunc=segfunc
        self.default=default
        self.size=pow(2,(size-1).bit_length())
        self.data=[default]*(self.size*2)
    def update(self,i,v):
        i+=self.size
        self.data[i]=v
        while i:
            i>>=1
            self.data[i]=self.segfunc(self.data[2*i],self.data[2*i+1])
    # 区間[l,r)に対するクエリ
    def query(self,l,r):
        l+=self.size
        r+=self.size
        lres,rres=self.default,self.default
        while l<r:
            if l&1:
                lres=self.segfunc(lres, self.data[l])
                l += 1
            if r&1:
                r-=1
                rres=self.segfunc(self.data[r],rres)
            l>>=1
            r>>=1
        res=self.segfunc(lres,rres)
        return res
    def get(self,i):
        return self.data[self.size+i]
    def add(self,i,v):
        self.update(i,self.get(i)+v)
    
#ary[0],ary[-1]
ml,mr=0,len(ary)+1
mv=0
st=SegmentTree(len(ary))
for qq in query:
    if qq[0]=='2':
        print(ary[ml],mv)
    else:
        _,a,b=map(int,qq.split())
        a=bisect_left(ary,a)
        st.add(0,-1)
        st.add(a,2)
        if ml<=a<mr:
            mv+=b
            ml,mr=a,a+1
        else:
            l,r=0,len(ary)+1
            mv+=b
            while r-l>1:
                x=(l+r)//2
                chk=st.query(0,x)
                if chk>=0:
                    l,r=l,x
                else:
                    l,r=x,r
            l0,r0=l,r
            l,r=ml,len(ary)+1
            while r-l>1:
                x=(l+r)//2
                chk=st.query(0,x)
                if chk>0:
                    l,r=l,x
                else:
                    l,r=x,r
            mv+=min(abs(ary[ml]-ary[l0]),abs(ary[mr]-ary[l0]))+abs(ary[a]-ary[l0])
            mr=l if st.query(0,l+1)>0 else l+1
            ml=l0 if st.query(0,l0+1)>=0 else l0+1

Submission status: Accepted

Solution code:
from bisect import bisect

Q = int(input())
xs = [-10 ** 10, 10 ** 10]
min_index = 0
minimum = 0
for _ in range(Q):
    s = input()
    if s[0] == '1':
        a, b = map(int, s[2:].split())
        index = bisect(xs, a)
        xs.insert(index, a)
        # f(xs[min_index]) == minimum を成立させるために調整。
        if min_index >= index:
            min_index += 1 
        minimum += abs(xs[min_index] - a) + b
        # min_indexがminを与えるように調整。minimumも同時に調整。
        if min_index < (len(xs) - 1) // 2:
            minimum += ((len(xs) % 2) - 2) * (xs[min_index + 1] - xs[min_index])
            min_index += 1
        elif min_index > (len(xs) - 1) // 2:
            minimum += (len(xs) % 2) * (xs[min_index - 1] - xs[min_index])
            min_index -= 1
    else:
        print(xs[min_index], minimum)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
class MedianContainer:
    def __init__(self):
        self._left_q = []
        self._right_q = []
        self._left_sum = 0
        self._right_sum = 0
        self._med1, self._med2 = None, None
        self._med = None

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

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


    def get_left_sum(self):
        return self._left_sum


    def get_right_sum(self):
        return self._right_sum


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

q = int(input())
const_b = 0
ansl = []

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


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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
class MedianContainer:
    def __init__(self):
        self._left_q = []
        self._right_q = []
        self._left_sum = 0
        self._right_sum = 0
        self._med1, self._med2 = None, None
        self._med = None

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

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


    def get_left_sum(self):
        return self._left_sum


    def get_right_sum(self):
        return self._right_sum


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


q = int(input())
ans = 0

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

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


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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

q = int(input())
ans = 0

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

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

        if first_flag:
            mid = a
            first_flag = False

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


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



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