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:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop
def solve(): 
    Q = int(input())
    q, a, b = map(int, input().split())
    B = b
    c = a
    L, R = [], []
    count = 1
    x = c
    v_ = 0
    res_l = []

    for _ in range(Q-1):
        #print(x, v_ ,c,L,R)
        *q_, = map(int, input().split())
        if q_[0] == 1:
            q, a, b = q_
            B += b
            if count&1:
                if a < c:
                    heappush(L, -a)
                    heappush(R, c)
                    x_ = -L[0]
                    v_ = x-x_
                    x = x_
                else:
                    heappush(L, -c)
                    heappush(R, a)                
            else:
                if a <= -L[0]:
                    heappush(L, -a)
                    x_ = c = -heappop(L)
                elif a >= R[0]:
                    heappush(R, a)
                    x_ = c = heappop(R)
                else:
                    x_ = c = a
                x = x_
                v_ += abs(x-a)
            count ^= 1
            #print(x, v_ ,c,L,R)
        else:
            v = v_ + B
            res_l.append('{} {}'.format(x, v))
    res = '\n'.join(res_l)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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

import sys
from heapq import heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

Q=INT()

li=[]
B=fx=cost=cnt=0
for _ in range(Q):
    instr=input()
    if instr[0]=='1':
        _,a,b=map(int, instr.split())
        B+=b
        heappush(li, a)
        if cnt==0:
            A=a
        else:
            # 偶数回目
            if cnt%2==1:
                A2=li[len(li)//2-1]
            # 奇数回目
            else:
                A2=li[len(li)//2]
            if a==A2:
                cost+=abs(a-A)
            else:
                cost+=abs(a-A2)
            A=A2
        fx=cost+B
        cnt+=1
    else:
        print(A, fx)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop
def solve(): 
    Q = int(input())
    q, a, b = map(int, input().split())
    B = b
    c = a
    L, R = [], []
    count = 1
    x = c
    v_ = 0
    res_l = []

    for _ in range(Q-1):
        #print(x, v_ ,c,L,R)
        *q_, = map(int, input().split())
        if q_[0] == 1:
            q, a, b = q_
            B += b
            if count&1:
                if a < c:
                    heappush(L, -a)
                    heappush(R, c)
                    x_ = -L[0]
                    v_ = x-x_
                    x = x_
                else:
                    heappush(L, -c)
                    heappush(R, a)                
            else:
                if a <= -L[0]:
                    heappush(L, -a)
                    x_ = -heappop(L)
                elif a >= R[0]:
                    heappush(R, a)
                    x_ = heappop(R)
                else:
                    x_ = c = a
                x = x_
                v_ += abs(x-a)
            count ^= 1
            #print(x, v_ ,c,L,R)
        else:
            v = v_ + B
            res_l.append('{} {}'.format(x, v))
    res = '\n'.join(res_l)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, absum, bsum, c = [], 0, 0, 0
left, right = -INF, INF
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        c += 1
        if left <= a <= right:
            left, right = a, a
            absum += 0
        elif a < left:
            left, right = ary[(c-1)//2], left
            absum += right - a
        else:
            left, right = right, ary[(c-1)//2 + 1]
            absum += a - left
        bsum += b

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    q = I()
    m = 0
    l = [-float("inf"),float("inf")]
    x = 0
    num = 0
    for _ in range(q):
        Q = LI()
        if len(Q) == 1:
            print(x,m)
        else:
            z,a,b = Q
            m += b
            if num == 0:
                num += 1
                l = [a,float("inf")]
                x = a
            elif num == 1:
                if a != l[0]:
                    num += 1
                    l = [min(a,l[0]),max(a,l[0])]
                    x = l[0]
                    m += l[1]-l[0]
            else:
                num += 1
                if num % 2:
                    if l[0] <= a < l[1]:
                        m += min(a-l[0],l[1]-a)
                        x = a
                    elif a < l[0]:
                        m += l[0]-a
                        x = l[0]
                        l = [a,l[1]]
                    else:
                        m += a-l[1]
                        x = l[1]
                        l = [l[0],a]
                else:
                    if l[0] <= a < l[1]:
                        if a < x:
                            m += x-a
                            l = [a,x]
                            x = a
                        else:
                            m += a-x
                            l = [x,a]
                    elif a < l[0]:
                        m += x-a
                        x = l[0]
                        l = [l[0],x]
                    else:
                        m += a-x
                        l = [x,l[1]]
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    q = I()
    m = 0
    l = [-float("inf"),float("inf")]
    x = 0
    num = 0
    for _ in range(q):
        Q = LI()
        if len(Q) == 1:
            print(x,m)
        else:
            z,a,b = Q
            m += b
            if num == 0:
                num += 1
                l = [a,float("inf")]
                x = a
            elif num == 1:
                if a != l[0]:
                    num += 1
                    l = [min(a,l[0]),max(a,l[0])]
                    x = l[0]
                    m += l[1]-l[0]
            else:
                num += 1
                if num % 2:
                    if l[0] <= a < l[1]:
                        x = a
                    elif a < l[0]:
                        m += l[0]-a
                        x = l[0]
                        l = [a,l[1]]
                    else:
                        m += a-l[1]
                        x = l[1]
                        l = [l[0],a]
                else:
                    if l[0] <= a < l[1]:
                        if a < x:
                            m += x-a
                            l = [a,x]
                            x = a
                        else:
                            m += a-x
                            l = [x,a]
                    elif a < l[0]:
                        m += x-a
                        x = l[0]
                        l = [l[0],x]
                    else:
                        m += a-x
                        l = [x,l[1]]
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
ans = []
Q = int(readline())

QL = [10**10]
QR = [10**10]
R = 0

for i in range(Q):
    t, *A = map(int, input().split())
    if t == 1:
        a, b = A
        R += b
        if -QL[0] <= a <= QR[0]:
            heappush(QL, -a)
            heappush(QR, a)
        elif a <= -QL[0]:
            heappush(QL, -a)
            heappush(QL, -a)
            c = heappop(QL)
            R += QL[0] - c
            heappush(QR, -c)
        elif QR[0] <= a:
            heappush(QR, a)
            heappush(QR, a)
            c = heappop(QR)
            R += QR[0] - c
            heappush(QL, -c)
    else:
        ans.append("%d %d\n" % (-QL[0], R))
sys.stdout.writelines(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
ans = []
Q = int(readline())

QL = [10**10]
QR = [10**10]
R = 0

for i in range(Q):
    t, *A = map(int, input().split())
    if t == 1:
        a, b = A
        R += b
        if -QL[0] <= a <= QR[0]:
            heappush(QL, -a)
            heappush(QR, a)
        elif a <= -QL[0]:
            heappush(QL, -a)
            heappush(QL, -a)
            c = heappop(QL)
            R += QL[0] - c
            heappush(QR, c)
        elif QR[0] <= a:
            heappush(QR, a)
            heappush(QR, a)
            c = heappop(QR)
            R += QR[0] - c
            heappush(QL, c)
    else:
        ans.append("%d %d\n" % (-QL[0], R))
sys.stdout.writelines(ans)

Submission status: Wrong Answer

Solution code:
import bisect

Q = int(input())

Query, A, B = [], [], 0
for _ in range(Q):
    q = tuple(map(int, input().split()))
    Query.append(q)
    if len(q) == 3:
        A.append(q[1])
        B += q[2]

A.sort()

lA = len(A)
if lA % 2 == 0:
    mi = lA // 2 - 1
    l, m, r = sum(A[:lA // 2]), 0, sum(A[lA // 2:])
    even = True
else:
    mi = lA // 2
    l, m, r = sum(A[:lA // 2]), A[lA // 2], sum(A[lA // 2 + 1:])
    even = False

ans = []
for i in range(Q):
    q = Query[Q - i - 1]
    if len(q) == 3:
        ix = bisect.bisect_left(A, q[1])
        if even:
            if ix > mi:
                l, r = l - A[mi], r - A[ix]
                mi = mi
            elif ix == mi:
                l, r = l - A[ix], r - A[mi + 1]
                mi = mi + 1
            else:
                l, r = l - A[ix], r - A[mi + 1]
                mi = mi + 1
            even = False
        else:
            if ix > mi:
                l, r = l, r - A[ix] + A[mi]
                mi = mi - 1
            elif ix == mi:
                l, r = l, r
                mi = mi - 1
            else:
                l, r = l - A[ix] + A[mi], r
                mi = mi
            even = True
        B -= q[2]
    else:
        ans.append((A[mi], r - l + B))

la = len(ans)
for i in range(la):
    print(ans[la - i - 1][0], ans[la - i - 1][1])

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())

alist = []
n = 0
bsum = 0
count = 0

for i in range(q):
    query = input()
    if query[0] == '1':
        que = query.split()
        a = int(que[1])
        b = int(que[2])
        heapq.heappush(alist, a)
        bsum += b
        n += 1
        if count == 0:
            f = 0
            m = n//2
            mid = alist[n//2]
            count += 1
        else:
            if alist[n//2] == mid:
                f += abs(alist[n//2] - a)
                mid = alist[n // 2]
                m = n // 2
            else:
                f += abs(mid - alist[n // 2]) * (n // 2 - (n - n // 2)) + abs(alist[n // 2] - a)
                mid = alist[n // 2]
                m = n // 2
    else:
        if len(alist) == 0:
            print(0, 0)
            continue
        x = alist[n//2]
        print(x, f+bsum)

Submission status: Wrong Answer

Solution code:
import heapq


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def absolute_minima():
    Q = int(input())

    L, R = PriorityQueue(), PriorityQueue()
    sL, sR = 0, 0
    M = None
    B = 0
    N = 0

    for _ in range(Q):
        query = [int(s) for s in input().split()]

        if query[0] == 1:
            _, a, b = query
            B += b
            N += 1

            if M is None:
                M = a
            elif M < a:
                R.enqueue(a)
                sR += a
            else:
                L.enqueue(a)
                sL += a

            while len(R)-len(L) > 1:
                L.enqueue(M)
                sL += M

                M = R.dequeue()
                sR -= M

            while len(L) > len(R):
                R.enqueue(M)
                sR += M

                M = L.dequeue()
                sL -= M

        else:
            s = - sL + sR + B
            if N % 2 == 0:
                s -= M
            print(M, s)


if __name__ == "__main__":
    absolute_minima()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N = int(input())
    Q = [ list(map(int,input().split())) for i in range(N) ]

    amin = float("inf")
    asum_p = 0
    asum_m = 0
    acnt_p = 0
    acnt_m = 0
    b = 0
    for q in Q:
        if q[0] == 1:
            amin = min(amin,q[1])
            if q[1] > 0:
                asum_p += q[1] 
                acnt_p += 1
            else:
                asum_m += q[1]
                acnt_m += 1
            b += q[2]
        else:
            res = 0
            res += asum_p - acnt_p*amin
            res += - asum_m + acnt_m*amin
            res += b

            print(amin, res)




    pass

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

Q = int(input())

Query, A, B = [], [], 0
for _ in range(Q):
    q = tuple(map(int, input().split()))
    Query.append(q)
    if len(q) == 3:
        A.append(q[1])
        B += q[2]

A.sort()

lA = len(A)
if lA % 2 == 0:
    mi = lA // 2 - 1
    l, m, r = sum(A[:lA // 2]), 0, sum(A[lA // 2:])
    even = True
else:
    mi = lA // 2
    l, m, r = sum(A[:lA // 2]), A[lA // 2], sum(A[lA // 2 + 1:])
    even = False

ans = []
for i in range(Q):
    q = Query[Q - i - 1]
    if len(q) == 3:
        ix = bisect.bisect_left(A, q[1])
        if even:
            if ix > mi:
                l, r = l - A[mi], r - A[ix]
                mi = mi
            elif ix == mi:
                l, r = l - A[ix], r - A[mi + 1]
                mi = mi + 1
            else:
                l, r = l - A[ix], r - A[mi + 1]
                mi = mi + 1
            even = False
        else:
            if ix > mi:
                l, r = l, r - A[ix] + m
                mi = mi - 1
            elif ix == mi:
                l, r = l, r
                mi = mi - 1
            else:
                l, r = l - A[ix] + m, r
                mi = mi
            even = True
        B -= q[2]
    else:
        ans.append((A[mi], r - l + B))

la = len(ans)
for i in range(la):
    print(ans[la - i - 1][0], ans[la - i - 1][1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

Q = int(input())
q = [list(map(int, input().split())) for _ in range(Q)]

def addT(n):
  k = 0
  while True:
    if T[k][0] >= n:
      T[k][1][1] += 1
      if T[k][1][0] == -1:
        T.append([n, [-1, 0], [-1, 0]])
        T[k][1][0] = t
        break
      else:
       k = T[k][1][0]
    else:
      T[k][2][1] += 1
      if T[k][2][0] == -1:
        T.append([n, [-1, 0], [-1, 0]])
        T[k][2][0] = t
        break
      else:
        k = T[k][2][0]

def getTmed(x, n):
  if T[x][1][1] == n - 1:
    return x
  elif T[x][1][1] > n - 1:
    return getTmed(T[x][1][0], n)
  else:
    return getTmed(T[x][2][0], n - (T[x][1][1] + 1))


T = []
b = 0
su = 0
for i in q:
  if T == []:
    T.append([i[1], [-1, 0], [-1, 0]])
    t = 1
    rk = i[1]
    b = i[2]
  elif i[0] == 2:
    k = getTmed(0, (t + 1) // 2)
    print(T[k][0], su + b)
  else:
    addT(i[1])
    k = getTmed(0, (t + 1) // 2)
    su += abs(T[k][0] - rk)
    rk = T[k][0]
    t += 1
    b += i[2]

Submission status: Wrong Answer

Solution code:
Q = int(input())
Queries = [list(map(int, input().split())) for _ in range(Q)]

import heapq as hp
L = [-(-(10**9+1))] # 最小ヒープなので負を入れる
R = [10**9+1] # そのまま
hp.heapify(L)
hp.heapify(R)
odd = False
sum_b = 0
sum_l = 0
sum_r = 0

flag = 1

for q in Queries:
  if len(q)==1 and q[0]==2:
    if flag ==0:
      print(*(-L[0], sum_b + abs(sum_l-sum_r)))
    else:
      print(*(-L[0], sum_b))
      flag = 1

  else:
    _, a, b = q
    sum_b += b

    l = -hp.heappop(L)
    r = hp.heappop(R)
    
    X = sorted([l, r, a])
    if odd==False:
      sum_l -= l
      sum_r -= r
      hp.heappush(L,-X[0])
      hp.heappush(L,-X[1])
      hp.heappush(R,X[2])
      sum_l += X[0]
      sum_r += X[2]
      odd=True
    elif odd==True:
      sum_r -= r
      hp.heappush(L,-X[0])
      hp.heappush(R,X[1])
      hp.heappush(R,X[2])
      sum_l += X[0]
      sum_r += X[1] + X[2]
      odd=False

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
l = []
c = 0

for i in range(n):
    a = list(map(int, input().split()))
    if a[0] == 1:
        bisect.insort(l,a[1])
        c += a[2]
    else:
        print(l[len(l)//2],sum([abs(i-l[len(l)//2]) for i in l])+c)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
from heapq import *


class StreamMedian(object):
    def __init__(self):
        self.less = []
        self.more = []

    def __repr__(self):
        return "less: {},  more: {}".format(self.less, self.more)

    def push(self, x):
        if not self.less:
            heappush(self.less, -x)
        else:
            if x < self.get():
                heappush(self.less, -x)
                if len(self.less) + 1 > len(self.more):
                    heappush(self.more, -heappop(self.less))
            else:
                heappush(self.more, x)
                if len(self.less) < len(self.more):
                    heappush(self.less, -heappop(self.more))

    def get(self):
        return -self.less[0]

    def diffsum(self, x):
        lesssum = sum(abs(x + xp) for xp in self.less)
        moresum = sum(abs(x - xp) for xp in self.more)
        return lesssum + moresum


Q = int(input())
box = StreamMedian()
offset = 0
for _ in range(Q):
    query = input()
    if query[0] == "1":
        a, b = map(int, query[1:].split())
        offset += b
        box.push(a)
    else:
        x = box.get()
        y = offset + box.diffsum(x)
        print(x, y)

Submission status: Wrong Answer

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

L, R = [], []
L_sum, R_sum = 0, 0
fq, fa, fb = map(int, input().split())
Median = fa
B = fb


for i in range(Q - 1):
    q = list(map(int, input().split()))
    if len(q) == 3:
        B += q[2]

        A = q[1]
        if A <= Median:
            heapq.heappush(R, Median)
            R_sum += Median
            L_sum += A
            Median = -heapq.heappushpop(L, -A)
            L_sum -= Median
        else:
            heapq.heappush(R, A)
            R_sum += A
    else:
        print(Median, abs(L_sum - (len(L) * Median)) + abs(R_sum - (len(R) * Median)) + B)

Submission status: Wrong Answer

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

L, R = [], []
L_sum, R_sum = 0, 0
fq, fa, fb = map(int, input().split())
Median = fa
B = fb


for i in range(Q - 1):
    q = list(map(int, input().split()))
    if len(q) == 3:
        B += q[2]

        A = q[1]
        if A <= Median:
            heapq.heappush(R, Median)
            R_sum += Median
            L_sum += A
            Median = -heapq.heappushpop(L, -A)
            L_sum -= Median
        else:
            heapq.heappush(R, A)
    else:
        print(Median, abs(L_sum - (len(L) * Median)) + abs(R_sum - (len(R) * Median)) + B)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

# class Node(object):
#     def __init__(self, value):
#         self.value = value
#         self.left = None
#         self.right: Node = None
#         self.parent: Node = None
#         self.isright = False
#
#     def add_node(self, node):
#         if node.value > self.value:
#             if self.right is None:
#                 self.right = node
#                 node.parent = self
#                 node.isright = True
#             else:
#                 self.right.add_node(node)
#         else:
#             if self.left is None:
#                 self.left = node
#                 node.parent = self
#                 node.isright = False
#             else:
#                 self.left.add_node(node)
#
#     def search_nearest_node(self, value):
#         if value > self.value:
#             if self.right is None:
#                 return self
#             else:
#                 return self.right.search_nearest_node(value)
#         else:
#             if self.left is None:
#                 return self
#             else:
#                 return self.left.search_nearest_node(value)
#
#     def find_lr_value(self, value):
#         nearest = self.search_nearest_node(value)
#         if nearest.value > value:
#             right = nearest.value
#             current = nearest
#             while True:
#                 if current.isright:
#                     break
#                 else:
#                     current = current.parent
#             left = current.value
#             return left, right
#
#         else:
#             left = nearest.value
#             current = nearest
#             while True:
#                 if not current.isright:
#                     break
#                 else:
#                     current = current.parent
#             right = current.value
#             return left, right
#
#     def calc(self, value):
#         result = abs(self.value -value)
#         if self.left is not None:
#             result += self.left.calc(value)
#         if self.right is not None:
#             result += self.right.calc(value)
#         return result
#

Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for query in qs:
    if query[0] == 1:
        pass
    else:
        print(1, 1)
    # if query[0] == 1:
    #     _, a, b = query
    #     b_all += b
    #     if tree is None:
    #         tree = Node(a)
    #     else:
    #         tree.add_node(Node(a))
    #     sum_value += a
    #     k_value += 1
    # else:
    #     weight = sum_value / k_value
    #     l, r = tree.find_lr_value(weight)
    #     targets = [int(math.floor(weight)), int(math.ceil(weight)), l, r]
    #     targets_values = [(target, tree.calc(target) + b_all) for target in targets]
    #     x,value = min(targets_values, key=lambda x: (x[1], x[0]))
    #     print(x, value)

exit(0)

Submission status: Wrong Answer

Solution code:
Q = int(input())
l, mid, r = None, None, None
s = 0
min_x = 0
for i in range(Q):
    q = list(map(int, input().split()))
    if len(q) == 1:
        print(min_x, s)
    else:
        a, b = q[1], q[2]
        s += b
        if mid == None:
            if l == None or r == None:
                mid = a
                min_x = a
            else:
                if a >= r:
                    s += a - r
                    mid = r
                    min_x = r
                elif a > l:
                    mid = a
                    min_x = a
                else:
                    s += l - a
                    mid = l
                    min_x = l
        else:
            if l == None or r == None:
                l, r = min(mid, a), max(mid, a)
                s += abs(l - r)
                min_x = l
            else:
                s += abs(a - mid)
                if a > r:
                    l, r = mid, r
                elif a >= l:
                    l, r = min(mid, a), max(mid, a)
                else:
                    l, r = a, l
                min_x = l
            mid = None

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import heapq
q=int(input())
_,a,b=map(int,input().split())
Small=[-a]
Large=[]
cnt=1
med=a
c=b
s=0
for i in range(q-1):
    query=tuple(map(int,input().split()))
    if query[0]==1:
        _,a,b=query
        c+=b
        if cnt%2:
            s+=abs(a-med)
            if a<-Small[0]:
                heapq.heappush(Small,-a)
                heapq.heappush(Large,-heapq.heappop(Small))
                med=-Small[0]
            else:
                heapq.heappush(Large,a)
        else:
            if a<=-Small[0]:
                heapq.heappush(Small,-a)
                med=-Small[0]
                s+=med-a
            elif a<=Large[0]:
                heapq.heappush(Small,-a)
            else:
                heapq.heappush(Large,a)
                med=heapq.heappop(Large)
                s+=a-med
                heapq.heappush(Small,-med)
        cnt+=1
    else:
        print(-Small[0],s+c)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

if __name__ == '__main__':
    q = int(input())
    query = [list(map(int, input().split())) for _ in range(q)]

    first_query = query[0]
    [_, a, b] = first_query
    a_list = [a]
    a_sum = 0
    b_sum = b
    state = [a]
    state_num = [1]
    center_index = 0
    mode = 0

    for que in query[1:]:
        # print(center_index)
        # print(state)
        # print(a_list)
        # print(b_sum)
        # print()
        if que[0] == 1:
            if mode == 0:
                insert_index = bisect_left(a_list, que[1])
                a_sum = a_sum + abs(state[0] - que[1])
                if center_index >= insert_index:
                    state = [que[1], state[0]]
                    center_index = insert_index
                else:
                    state = [state[0], que[1]]
                    # center_index = center_index
                mode = 1
            else:
                insert_index = bisect_left(a_list, que[1])
                if center_index + 1 == insert_index:
                    state = [que[1]]
                elif center_index >= insert_index:
                    state = [state[0]]
                else:
                    state = [state[1]]
                a_sum = a_sum + abs(state[0] - que[1])
                center_index = center_index + 1
                mode = 0
            a_list.insert(insert_index, que[1])
            b_sum = b_sum + que[2]
        else:
            min_x = state[0]
            print(min_x, a_sum + b_sum)

# 状態の更新
# 中央がある（中央）
# 　中央より左　→　中央がない（中央の１つ左　中央）
# 　中央より右　→　中央がない（中央　中央の１つ右）
# 中央がない（中央左　中央右）
# 　中央左より左　→　中央がある（中央左）
# 　中央左と中央右の間　→　中央がある（新しい値）
# 　中央右より右　→　中央がある（中央右）

# 求値
# 　中央、または、中央左がXとなる
# 　XとAと（Bの和）から最小値を計算する

# |x - a|
# x - a  x-a >= 0
# a - x  x-a < 0
# center_indexの部分で切り替わる