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: Wrong Answer

Solution code:
a_s = []
b = 0
q = int(input())
def binary_search(arr, low, high, x): 
    # Check base case 
    if high >= low: 
        mid = (high + low) // 2
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return mid 
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 
        # Else the element can only be present in right subarray 
        else: 
            return binary_search(arr, mid + 1, high, x) 
    else: 
        # Element is not present in the array 
        return low

last_2 = -1
last_2_in = None
for i in range(q):
    # print(a_s)
    s = [int(i) for i in input().split()]
    if len(s )!= 1:
        a = s[1]
        b += s[2]
        l_0 = len(a_s)
        nearest_el = binary_search(a_s, 0, len(a_s) - 1, a)
        a_s = a_s[:nearest_el] + [a] + a_s[nearest_el:]
        if len(a_s) == l_0: a_s.append(a)
    else:
        if len(a_s) == last_2:
            print(*last_2_in)
        else:
            x = a_s[max(len(a_s)//2-1, 0)]
            y = b
            for j in range(len(a_s)):
                y += abs(x-a_s[j])
            print(x, y)
            last_2 = len(a_s)
            last_2_in = (x, y)

Submission status: Wrong Answer

Solution code:
import math

class Avltree:
    """
    AVL木

    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"

    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None

    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans

    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans

    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key

    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key

    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr

    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl

    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr

    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl

    def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else:
            p.right = v

    def insert(self, key):  # rootでのみ呼ばれる挿入
        if self.key is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite

    def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break

    def to_s(self):
        return self.key

    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key

    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key


b_sum = 0
left_sum = 0
right_sum = 0
piv = None
Q = int(input())
cnt = 0
bt = Avltree()
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        a, b = q[1], q[2]
        b_sum += b
        bt.insert(a)
        """
        if piv is None:
            piv = a
        elif cnt % 2 == 0:
            if a <= piv:
                left_sum += (piv - a)
            else:
                np = bt.search_higher(piv, math.inf)
                left_sum += (np - piv) * (cnt // 2)
                right_sum -= (np - piv) * (cnt // 2)
                right_sum += a - np
                piv = np
        elif cnt % 2 == 1:
            if a < piv:
                np = bt.search_lower(piv, -1*math.inf)
                left_sum -= (piv - np) * (cnt // 2)
                right_sum += (piv - np) * (cnt // 2 + 1)
                left_sum += (np-a)
                piv = np
            else:
                right_sum += (a - piv)
        cnt += 1

    elif q[0] == 2:
        ans = b_sum + left_sum + right_sum
        print(piv, ans)
"""

Submission status: Wrong Answer

Solution code:
Q = int(input())
A = []
B = []
for _ in range(Q):
    qry = list(map(int,input().split()))
    if len(qry)>1:
        A.append(qry[1])
        B.append(qry[2])
    else:
        low = -10**9
        high = 10**9
        while high-low>2:
            midl = (2*low+high)//3
            midh = (low+2*high)//3
            a = 0
            for i in range(len(A)):
                a += abs(A[i]-midl)+B[i]
            b = 0
            for i in range(len(A)):
                b += abs(A[i]-midh)+B[i]
            if a>b:
                low = midl
            else:
                high = midh
        mid = (low+high)//2
        a = 0
        for i in range(len(A)):
            a += abs(A[i]-mid)+B[i]
        print(mid,a)

Submission status: Wrong Answer

Solution code:
from heapq import heappush

Q=int(input())
A = []
bsum=0
for i in range(Q):
  q = input()
  if q[0]=='1':
    _,a,b = map(int,q.split())
    heappush(A,a)
    bsum += b
  else:
    if len(A)%2:
      amed = A[len(A)//2]
    else:
      amed = A[len(A)//2-1]
    print(amed,sum(abs(amed-a) for a in A)+bsum)

Submission status: Wrong Answer

Solution code:
from heapq import heappush

Q=int(input())
INF=10**10
A = []
asum=0
bsum=0
for i in range(Q):
  q = input()
  if q[0]=='1':
    _,a,b = map(int,q.split())
    heappush(A,a)
    asum += a
    bsum += b
  else:
    amin,amax = A[0],A[-1]
    if len(A)%2:
      amed = A[len(A)//2]
    else:
      amed = (A[len(A)//2-1] + A[len(A)//2-1])//2
    print(amed,sum(abs(amed-a) for a in A)+bsum)

Submission status: Wrong Answer

Solution code:
from heapq import heappush

Q=int(input())
INF=10**10
A = []
bsum=0
for i in range(Q):
  q = input()
  if q[0]=='1':
    _,a,b = map(int,q.split())
    heappush(A,a)
    bsum += b
  else:
    amin,amax = A[0],A[-1]
    if len(A)%2:
      amed = A[len(A)//2]
    else:
      amed = (A[len(A)//2-1] + A[len(A)//2-1])//2
    print(amed,amax-amin+bsum)

Submission status: Wrong Answer

Solution code:
Q=int(input())
INF=10**10
amin=INF
amax=-INF
bsum=0
for i in range(Q):
  q = input()
  if q[0]=='1':
    _,a,b = map(int,q.split())
    amax = max(amax,a)
    amin = min(amin,a)
    bsum += b
  else:
    print(amin,amax-amin+bsum)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
q = int(input())
Q = [list(map(int,input().split())) for i in range(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

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)

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)
        if ok_a % 2 == 0 and D[(Q[i][1], i)] > m_ind:
            ok = 0
            ng = 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:
            ok = 0
            # print("ok_a", ok_a)
            # print(print_bit(B))
            ng = 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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    Q=ii()

    max_a = -INF
    min_a = INF

    a_sum = 0
    b_sum = 0
    n = 0
    for q in range(Q):
        S = input()
        if S == "2":
            y = INF
            ans = INF
            for x in [min_a,max_a]:
                if x == INF or x == -INF: continue
                ny = abs(n*x-a_sum) + b_sum # 三角不等式
                if y > ny:
                    y = ny
                    ans = min(ans,x)
            
            assert y != INF
            print(ans,y)
        
        else:
            _,a,b = map(int,S.split())
            max_a = max(max_a,a)
            min_a = min(min_a,a)
            a_sum += a
            b_sum += b
            n += 1






if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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[a])),ACC2.query(dic[x]+1,dic[x]+2),(10**10-x)*(B.sum(dic[a]-1)),base)
    print(x,ACC1.query(dic[x]+1,dic[x]+2)-(x+10**10)*(count-B.sum(dic[a]))+ACC2.query(dic[x]+1,dic[x]+2)+(10**10-x)*(B.sum(dic[a]-1))+base)

Submission status: Wrong Answer

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}
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
  
B = BIT(int_log(len(As),2)+1)

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

Submission status: Wrong Answer

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[l]),abs(ary[mr]-1-ary[l]))+abs(ary[a]-ary[l])
            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: Wrong Answer

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+=min(abs(ary[ml]-ary[a]),abs(ary[mr]-1-ary[a]))
            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
            ml=l if st.query(0,l+1)>=0 else l+1
            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
            mr=l if st.query(0,l+1)>0 else l+1