Problem: 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.

Submission attempts (in order):



import sys
input = sys.stdin.readline
import heapq

Q = int(input())


L = [] 
R = []
L_size = 0
R_size = 0
min_value = 0
min_x = 0

INF = 10**18
L_max = -INF
R_min = INF

def f1(a,b):
  global min_value,L_max,R_min,min_x,L_size,R_size
  min_value += b
  if a < L_max:
    heapq.heappush(L,-a)
    L_size += 1
    if L_size == R_size:
      min_value += min_x - a
      return
    elif L_size == R_size + 1:
      min_x = L_max
      min_value += min_x - a
      return
    else:
      
      L_size -= 1
      R_size += 1
      x = -heapq.heappop(L)
      heapq.heappush(R,x)
      L_max = -heapq.nsmallest(1,L)[0]
      R_min = x
      min_x = x
      min_value += x-a
      return
  elif a > R_min:
    heapq.heappush(R,a)
    R_size += 1
    if L_size == R_size:
      min_value += a - min_x
      return
    elif R_size == L_size + 1:
      min_x = R_min
      min_value += a - min_x
      return
    else:
      
      R_size -= 1
      L_size += 1
      x = heapq.heappop(R)
      heapq.heappush(L,-x)
      R_min = heapq.nsmallest(1,R)[0]
      L_max = x
      min_x = x
      min_value += a-x
      return
  else:
    if L_size > R_size:
      heapq.heappush(R,a)
      R_size += 1
      R_min = a
      min_x = a
      min_value += a-L_max
      return
    elif R_size > L_size:
      heapq.heappush(L,-a)
      L_size += 1
      L_max = a
      min_x = a
      min_value += R_min - a
      return
    else: 
      heapq.heappush(L,-a)
      L_size += 1
      L_max = a
      min_x = a
      return

def f2():
  print(min_x,min_value)
  
for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()



Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(L,1)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  q = [int(x) for x in input().split()]
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()






import heapq

Q = int(input())


L = [] 
R = []
L_size = 0
R_size = 0
min_value = 0
min_x = 0

INF = 10**18
L_max = -INF
R_min = INF

def f1(a,b):
  global min_value,L_max,R_min,min_x,L_size,R_size
  min_value += b
  if a < L_max:
    heapq.heappush(L,-a)
    L_size += 1
    if L_size == R_size:
      min_value = min_x - a
      return
    elif L_size == R_size + 1:
      min_x = L_max
      min_value += min_x - a
      return
    else:
      
      x = -heapq.heappop(L)
      heapq.heappush(R,x)
      L_max = -heapq.nsmallest(1,L)[0]
      R_min = x
      min_x = x
      min_value += x-a
      return
  elif a > R_min:
    heapq.heappush(R,a)
    R_size += 1
    if L_size == R_size:
      min_value = a - min_x
      return
    elif R_size == L_size + 1:
      min_x = R_min
      min_value += a - min_x
      return
    else:
      
      x = heapq.heappop(R)
      heapq.heappush(L,-x)
      R_min = heapq.nsmallest(1,R)[0]
      R_min = x
      min_x = x
      min_value += a-x
      return
  else:
    if L_size > R_size:
      heapq.heappush(R,a)
      R_size += 1
      R_min = a
      min_x = a
      min_value += a-L_max
      return
    elif R_size > L_size:
      heapq.heappush(L,-a)
      L_size += 1
      L_max = a
      min_x = a
      min_value += R_min - a
      return
    else: 
      heapq.heappush(L,-a)
      L_size += 1
      L_max = a
      min_x = a
      return

def f2():
  print(min_x,min_value)
  
for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()
    







import sys
input = sys.stdin.readline
import heapq

Q = int(input())


L = [] 
R = []
L_size = 0
R_size = 0
min_value = 0
min_x = 0

INF = 10**18
L_max = -INF
R_min = INF

def f1(a,b):
  global min_value,L_max,R_min,min_x,L_size,R_size
  min_value += b
  if a < L_max:
    heapq.heappush(L,-a)
    L_size += 1
    if L_size == R_size:
      min_value += min_x - a
      return
    elif L_size == R_size + 1:
      min_x = L_max
      min_value += min_x - a
      return
    else:
      
      x = -heapq.heappop(L)
      heapq.heappush(R,x)
      L_max = -heapq.nsmallest(1,L)[0]
      R_min = x
      min_x = x
      min_value += x-a
      return
  elif a > R_min:
    heapq.heappush(R,a)
    R_size += 1
    if L_size == R_size:
      min_value += a - min_x
      return
    elif R_size == L_size + 1:
      min_x = R_min
      min_value += a - min_x
      return
    else:
      
      x = heapq.heappop(R)
      heapq.heappush(L,-x)
      R_min = heapq.nsmallest(1,R)[0]
      R_min = x
      min_x = x
      min_value += a-x
      return
  else:
    if L_size > R_size:
      heapq.heappush(R,a)
      R_size += 1
      R_min = a
      min_x = a
      min_value += a-L_max
      return
    elif R_size > L_size:
      heapq.heappush(L,-a)
      L_size += 1
      L_max = a
      min_x = a
      min_value += R_min - a
      return
    else: 
      heapq.heappush(L,-a)
      L_size += 1
      L_max = a
      min_x = a
      return

def f2():
  print(min_x,min_value)
  
for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()
    




Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(L,1)
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  q = [int(x) for x in input().split()]
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop, heappushpop

Q = int(readline())
query = (tuple(map(int,line.split())) for line in readlines())


INF = 10**12
L = [INF] 
R = [INF]
sumL = 0; sumR = 0 
lenL = 0; lenR = 0 

add = 0 

answer = []
for q in query:
    if len(q) == 1:
        
        x = -L[0]
        f = sumR - sumL + x * (lenL - lenR)
        answer.append('{} {}'.format(x,f+add))
        continue
    
    a,b = q[1:]
    add += b
    if lenL > lenR:
        sumL += a; a = -heappushpop(L,-a); sumL -= a
        heappush(R,a); sumR += a; lenR += 1
    else:
        sumR += a; a = heappushpop(R,a); sumR -= a
        heappush(L,-a); sumL += a; lenL += 1

print('\n'.join(answer))

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Accepted