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 sys
from heapq import heappop, heappush


def main():
    input = sys.stdin.readline
    INF = 10**9 + 1
    Q = int(input())
    left = []
    right = []
    min_val = 0
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            a, b = q[1], q[2]

            # Update median
            heappush(left, -a)
            heappush(right, a)

            left_max = -heappop(left)
            right_min = heappop(right)

            heappush(left, -min(left_max, right_min))
            heappush(right, max(left_max, right_min))

            # Update minimum value of f(x)
            min_val += abs(right_min - left_max)
            min_val += b

        else:
            median = -heappop(left)
            print('{} {}'.format(median, min_val))

            heappush(left, -median)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush


def main():
    input = sys.stdin.readline
    INF = 10**9 + 1
    Q = int(input())
    left = []
    right = []
    min_val = 0
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            a, b = q[1], q[2]

            # Update median
            heappush(left, -a)
            heappush(right, a)

            left_max = -heappop(left)
            right_min = heappop(right)

            median_left = min(left_max, right_min)
            median_right = max(left_max, right_min)

            heappush(left, -median_left)
            heappush(right, median_right)

            # Update minimum value of f(x)
            min_val += median_right - median_left
            min_val += b

        else:
            median = -heappop(left)
            print('{} {}'.format(median, min_val))

            heappush(left, -median)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush


def main():
    input = sys.stdin.readline
    INF = 10**9 + 1
    Q = int(input())
    left = []
    right = []
    min_val = 0
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            a, b = q[1], q[2]

            # Update median
            heappush(left, -a)
            heappush(right, a)

            left_max = -heappop(left)
            right_min = heappop(right)

            median_left = min(left_max, right_min)
            median_right = max(left_max, right_min)

            heappush(left, -median_left)
            heappush(right, median_right)

            # Update minimum value of f(x)
            min_val += abs(median_right - median_left)
            min_val += b

        else:
            median = -heappop(left)
            print('{} {}'.format(median, min_val))

            heappush(left, -median)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import sys

# from matplotlib import pyplot as plt

sys.setrecursionlimit(10000)
INF = float('inf')

Q = int(next(sys.stdin))

# def plot(fn):
#     x = np.arange(-10, 10, 1)
#     y = np.array([fn(xa) for xa in x])
#     plt.plot(x, y)
#     plt.grid()
#     plt.show()
#
#
# def g(fn, a, b):
#     return lambda x: fn(x) + abs(x - a) + b
#
#
# f = lambda x: 0
# i = 0
# for _ in range(Q):
#     q = list(map(int, input().split()))
#     if q[0] == 1:
#         a, b = q[1], q[2]
#         f = g(f, a, b)
#     else:
#         plot(f)


# a をソートしたときに真ん中に来る値 x が最小値を持つ
# 中央値しか必要ないのでヒープ 2 つ作って管理
# 中央値より小さいやつ
smalls = []
# 中央値より大きいやつ
larges = []
# こたえ f(x) の最小値
fmin = 0
prev_x = None
for _ in range(Q):
    q = list(map(int, next(sys.stdin).split()))
    if q[0] == 1:
        a, b = q[1], q[2]

        # 適切な方に入れる
        if not larges or a > larges[0]:
            heapq.heappush(larges, a)
        else:
            heapq.heappush(smalls, -a)
        # 偏り解消
        if len(larges) > len(smalls) + 1:
            heapq.heappush(smalls, -heapq.heappop(larges))
        elif len(smalls) > len(larges) + 1:
            heapq.heappush(larges, -heapq.heappop(smalls))

        # x は a の中央値
        if len(smalls) >= len(larges):
            x = -smalls[0]
        else:
            x = larges[0]

        fmin += abs(x - a) + b
        if x != prev_x:
            if prev_x is not None and len(smalls) == len(larges):
                fmin += abs(x - prev_x)
            prev_x = x
    else:
        if len(smalls) >= len(larges):
            x = -smalls[0]
        else:
            x = larges[0]
        print(x, fmin)

Submission status: Accepted

Solution code:
from heapq import heappushpop, heappush
left, right = [], []
q = int(input())
ans = 0
for _ in range(q):
	a = list(map(int, input().split()))
	if a[0] == 1:
		left_out = heappushpop(left, -a[1])
		right_out = heappushpop(right, a[1])
		ans += a[2] + abs(left_out+right_out)
		heappush(left, -right_out)
		heappush(right, -left_out)
	else:
		print(-left[0], ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heappushpop
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(R, -heappushpop(L, -q[1]))
        else:
            heappush(R, q[1])
            heappush(L, -heappushpop(R, q[1]))
    else:
        print(-L[0], B+M)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heappushpop
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(R, -heappushpop(L, -q[1]))
        else:
            heappush(R, q[1])
            heappush(L, -heappushpop(R, q[1]))
    else:
        print(-L[0], B+M)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(L, -q[1])
            heappush(R, -heappop(L))
        else:
            heappush(R, q[1])
            heappush(R, q[1])
            heappush(L, -heappop(R))
    else:
        print(-L[0], B+M)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    q = I()
    aa = [LI() for _ in range(q)]

    bt = aa[0][2]
    m = 2 ** 20
    c = collections.defaultdict(int)
    lq = [inf]
    rq = [inf]
    c[-inf] = 1
    c[inf] = 1
    x = aa[0][1]
    c[x] = 1
    xl = 0
    lc = 0
    xr = 0
    rc = 0
    r = []
    for t in aa[1:]:
        if t[0] == 2:
            r.append('{} {}'.format(x, xl+xr+bt))
        else:
            _,a,b = t
            bt += b
            if a == x:
                c[x] += 1
                continue
            c[a] += 1
            if c[a] == 1:
                if a < x:
                    heapq.heappush(lq,-a)
                else:
                    heapq.heappush(rq,a)
            xc = c[x]
            if a < x:
                xl += x - a
                lc += 1
                t = xl + xr
                nx = -lq[0]
                nc = c[nx]
                s = x - nx
                nt = xl - lc * s + xr + (rc+xc) * s
                if nt <= t:
                    xl -= lc * s
                    xr += (rc+xc) * s
                    lc -= nc
                    rc += xc
                    heapq.heappush(rq,x)
                    x = nx
                    heapq.heappop(lq)
            else:
                xr += a - x
                rc += 1
                t = xl + xr
                nx = rq[0]
                nc = c[nx]
                s = nx - x
                nt = xl + (lc+xc) * s + xr - rc * s
                if nt < t:
                    xl += (lc+xc) * s
                    xr -= rc * s
                    lc += xc
                    rc -= nc
                    heapq.heappush(lq,-x)
                    x = nx
                    heapq.heappop(rq)

    return '\n'.join(r)


print(main())

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from heapq import heappush,heappop

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))

def main():
    Q = int(input())
    sb = 0
    lupper = []
    rlower = []
    s = 0
    for _ in range(Q):
        cmds = tuple(map(int,input().split()))
        if cmds[0]==1:
            _,a,b = cmds
            sb+= b
            if len(lupper)== 0 or a<=-lupper[0]:
                heappush(lupper,-a)
                s+=-lupper[0]-a
                if len(lupper)-len(rlower)>=2:
                    heappush(rlower,-heappop(lupper))
            else:
                heappush(rlower,a)
                s+=a+lupper[0]
                if len(rlower)>len(lupper):
                    s+=-lupper[0]-rlower[0]
                    heappush(lupper,-heappop(rlower))  
        else:
            print (-lupper[0], s+sb)
    
main()

Submission status: Accepted

Solution code:
import bisect
from heapq import heappush as hpush 
from heapq import heappushpop as hpushpop 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                hpushpop(l,-q1)
            else:
                hpushpop(r,q1)

        else:
            if q1<-l[0]:
                hpush(l,-q1)
                hpush(r,-l[0])
            else:
                hpush(r,q1)
                hpush(l,-r[0])
        

        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,a+b)

Submission status: Accepted

Solution code:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<-l[0]:
                heapq.heappush(l,-q1)
                heapq.heappush(r,-l[0])
            else:
                heapq.heappush(r,q1)
                heapq.heappush(l,-r[0])
        

        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,a+b)

Submission status: Accepted

Solution code:
import heapq

Q = int(input())
b_sum = 0
a_list = []
left = []
right = []
res = 0

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        b_sum += query[2]
        if len(right) == 0:
            a = query[1]
            heapq.heappush(right, -a)
        else:
            res += abs(query[1] + right[0])
            if query[1] <= -right[0]:
                heapq.heappush(right, -query[1])
            else:
                heapq.heappush(left, query[1])
        if len(right) < len(left):
            x = heapq.heappop(left)
            y = -right[0]
            res += y - x
            heapq.heappush(right, -x)
        elif len(right) > len(left) + 1:
            x = - heapq.heappop(right)
            heapq.heappush(left, x)
    else:
        print(-right[0], res + b_sum)

Submission status: Accepted

Solution code:
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 reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

# bit = Bit(10)
# bit.add(1, 1)
# bit.add(1, 1)

# # bit.add(2, 2)
# # bit.add(3, 3)
# print(bit.sum(1))

N=int(input())
queries = [tuple(map(int, input().split())) for _ in range(N)]

numl = []
for q in queries:
    if q[0] == 1:
        numl.append(q[1])
numl.sort()
val_to_key = {}

for i,v in enumerate(numl):
    if not v in val_to_key:
        val_to_key[v] = i

# print(numl)
# print(val_to_key)

cum_b = 0
cum_a = 0
bit = Bit(200005)
bit2 = Bit(200005)
cnt = 0

def abs_sum(mid):
    loc_sum = bit.sum(mid+1)
    lft_cnt = bit2.sum(mid+1)
    lef_sum = numl[mid]*lft_cnt - loc_sum
    rig_sum = cum_a-loc_sum - numl[mid]*(cnt-lft_cnt)
    return lef_sum + rig_sum

def solve(cntmid):
    left = 0
    right = len(numl)
    while left < right:
        mid = (left + right) // 2
        # print(mid+1)
        nums = bit2.sum(mid+1)
        if nums < cntmid:
            left = mid + 1
        else:
            right = mid
    return numl[left], abs_sum(left)+cum_b

for qu in queries:
    if qu[0] ==  1:
        _, a, b = qu
        # print(val_to_key[a])
        bit.add(val_to_key[a]+1, a)
        bit2.add(val_to_key[a]+1, 1)
        cnt += 1
        cum_b += b
        cum_a += a
    else:
        if cnt % 2 == 0:
            sol, val = solve(cnt//2)
            sol2, val2 = solve(cnt//2+1)
            if val > val2: sol, val = sol2, val2
        else:
            sol, val = solve(cnt//2+1)
        print("{} {}".format(sol, val))

# cum = 0
# lis = []
# for _ in range(N):
#     qu=list(map(int, input().split()))
#     if qu[0] == 1:
#         lis.append(qu[1])
#         cum += qu[2]
#     else:

Submission status: Accepted

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

b = 0
mid = None
lq = []
ls = 0
rq = []
rs = 0
n = 0

for _ in range(Q):
    q = input()
    if q[0] == '1':
        x, y, z = map(int, q.split())
        if n == 0:
            mid = y
        elif mid is None:
            l = -lq[0]     
            r = rq[0]
            if y<l:
                mid = -heapq.heappop(lq)
                heapq.heappush(lq, -y)
                ls = ls-mid+y
            elif y<r:
                mid = y
            else:
                mid = heapq.heappop(rq)
                heapq.heappush(rq, y)
                rs = rs-mid+y
        else:
            heapq.heappush(lq, -min(y, mid))
            heapq.heappush(rq, max(y, mid))
            ls = ls+min(y, mid)
            rs = rs+max(y, mid)
            mid = None
            
        n += 1
        b += z
    else:
        if mid is None:
            print(-lq[0], b-ls+rs)
        else:
            print(mid, b-ls+rs)

Submission status: Accepted

Solution code:
# import numpy as np
# from collections import defaultdict
# from functools import reduce

import heapq

# s = input()
Q = int(input())
# A = list(map(int, input().split()))
# n, m, k = map(int, input().split())


A_left_sum = 0
A_left = []
A_right_sum = 0
A_right = []
A_med = None
query_size = 0
b_sum = 0

# n = len(As)
# n is odd:
# A_left + As[n//2] + B_left
# n is even:
# A_left + B_left

for i in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
      a =  query[1]
      if A_med is None:
        A_med = a
      else:
        if query_size%2 == 0: # even
          left_max = -A_left[0]
          right_min = A_right[0]
          if a < left_max:
            heapq.heappushpop(A_left, -a)
            A_left_sum += a - left_max
            A_med = left_max
          elif a > right_min:
            heapq.heappushpop(A_right, a)
            A_right_sum += a - right_min
            A_med = right_min
          else:
            A_med = a
        else: # odd
          if A_med <= a:
            heapq.heappush(A_left, -A_med)
            heapq.heappush(A_right, a)
            A_left_sum += A_med
            A_right_sum += a
          else:
            heapq.heappush(A_left, -a)
            heapq.heappush(A_right, A_med)
            A_right_sum += A_med
            A_left_sum += a

      # print(As)
      # print(A_left)
      # print(A_right)
      query_size += 1

      b_sum += query[2]
    else:
      if query_size%2 == 0: #even
        print(-A_left[0], A_right_sum - A_left_sum + b_sum)
      else:
        print(A_med, A_right_sum - A_left_sum + b_sum)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = int(input())
s = list(map(int,input().split()))
a, b = s[1], s[2]
L = []
R = []
heappush(L,-a)
heappush(R,a)

bsum = b
t = 0
for k in range(N-1):
    s = input()
    if s[0] == "1":
        s = list(map(int,s.split()))
        a = s[1]
        b = s[2]
        bsum += b
        if -L[0] <= a <= R[0]:
            pass
        else:
            t += min(abs(a+L[0]),abs(a-R[0]))
        heappush(L,-a)
        heappush(R,a)
        if -L[0] > R[0]:
            c = heappop(L)
            d = heappop(R)
            heappush(R,-c)
            heappush(L,-d)
    else:
        print(-L[0], t+bsum)

Submission status: Accepted

Solution code:
import heapq

Q = int(input())

A_left = [] #最大を取り出すのでminus queueにする
A_right = [] #最小を取り出す
A_middle = 0
A_size = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        A_size+=1
        sabun = 0
        if A_size==1: #初期設定
            A_middle = a
            sabun = 0
        elif A_size%2==0: #偶数処理
            if a <= A_middle:
                sabun = A_middle - a
                heapq.heappush(A_left,a*(-1))
                heapq.heappush(A_right,A_middle)
            else:
                sabun = a - A_middle
                heapq.heappush(A_left,A_middle*(-1))
                heapq.heappush(A_right,a)
            A_middle = 0 #デバッグ用
        else: #奇数処理
            if a<A_left[0]*(-1):
                sabun = A_left[0]*(-1) - a
                A_middle = heapq.heappop(A_left)*(-1)
                heapq.heappush(A_left,a*(-1))
            elif a>A_right[0]:
                sabun = a - A_right[0]
                A_middle = heapq.heappop(A_right)
                heapq.heappush(A_right,a)
            else:
                sabun = 0
                A_middle = a
        MIN_SCORE += sabun + b if A_size>1 else b
    elif q[0]=="2":
        if A_size%2==0:
            print(A_left[0]*(-1),MIN_SCORE)
        else:
            print(A_middle,MIN_SCORE)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
q = int(input())
tei = 0
x = []
nnn = []
import bisect
def press(a):
    n = len(a)
    b = set(a)
    b = list(b)
    b.sort()
    c = [0] * n
    for i in range(n):
        c[i] = bisect.bisect_left(b,a[i])
    return b,c
for i in range(q):
        nnn.append(input().rstrip())
for i in range(q):
        nn = nnn[i]
        if int(nn[0]) == 1:
                _,a,b = map(int,nn.split())
                x.append(a)
x.sort()
mo,za = press(x)
mo = x
d = dict()
for i in range(len(x)):
        d[mo[i]] = za[i]+1
dg = dict()
for i in range(len(x)):
        dg[za[i]+1] = mo[i]
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
bit1 = BIT(len(x))
bit2 = BIT(len(x))
now = -1
def cheak(x,y):
  o = bit2.sum(x)
  if y >= o:
    return 0
  else:
    return 1
for i in range(q):
        nn = nnn[i]
        if int(nn[0]) == 1:
                _,a,b = map(int,nn.split())
                tei += b
                bit1.add(d[a],a)
                bit2.add(d[a],1)
                now += 1
        else:
                dai = len(x)
                syo = 1
                while True:
                        if dai-syo <= 1:
                                if cheak(syo,now//2) == 1:
                                        dai = syo
                                break
                        kon = (dai+syo)//2
                        c = cheak(kon,now//2)
                        if c == 1:
                                dai = kon
                        else:
                                syo = kon
                ans = 0
                ans -= bit1.sum(dai) - dg[dai]*bit2.sum(dai)
                ans += bit1.sum(len(x)) -bit1.sum(dai) -((bit2.sum(len(x))-bit2.sum(dai))*dg[dai])
                print(dg[dai],tei+ans)

Submission status: Accepted

Solution code:
import heapq

def calc(keisuu_lower_max, keisuu_lower_sum,  keisuu_lower_count,
         keisuu_upper_sum, keisuu_upper_count, teisuu):
    print(keisuu_lower_max,
          - keisuu_lower_sum + keisuu_lower_count * keisuu_lower_max
          + keisuu_upper_sum - keisuu_upper_count * keisuu_lower_max + teisuu)


def lowerpush(keisuu_lower, a, keisuu_lower_max,  keisuu_lower_sum, keisuu_lower_count):
    heapq.heappush(keisuu_lower, -a)
    keisuu_lower_count += 1
    keisuu_lower_max = -keisuu_lower[0]
    keisuu_lower_sum += a
    return keisuu_lower, a, keisuu_lower_max,  keisuu_lower_sum, keisuu_lower_count


def upperpush(keisuu_upper, a, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count):
    heapq.heappush(keisuu_upper, a)
    keisuu_upper_count += 1
    keisuu_upper_min = keisuu_upper[0]
    keisuu_upper_sum += a
    return keisuu_upper, a, keisuu_upper_min,  keisuu_upper_sum, keisuu_upper_count


def from_lower_to_upper(keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count,
                        keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count):

    e = -heapq.heappop(keisuu_lower)
    heapq.heappush(keisuu_upper, e)
    keisuu_lower_sum -= e
    keisuu_upper_sum += e
    keisuu_lower_max = -keisuu_lower[0]
    keisuu_upper_min = e
    keisuu_lower_count -= 1
    keisuu_upper_count += 1

    return keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count, keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count


def from_upper_to_lower(keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count,
                        keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count):

    d = heapq.heappop(keisuu_upper)
    heapq.heappush(keisuu_lower, -d)
    keisuu_lower_sum += d
    keisuu_upper_sum -= d
    keisuu_lower_max = d
    keisuu_upper_min = keisuu_upper[0]
    keisuu_lower_count += 1
    keisuu_upper_count -= 1

    return keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count, keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count


def main():
    q = int(input())
    keisuu_lower = []
    keisuu_upper = []
    keisuu_lower_max = 0
    keisuu_upper_min = float("inf")
    keisuu_lower_count = 0
    keisuu_upper_count = 0
    keisuu_lower_sum = 0
    keisuu_upper_sum = 0
    teisuu = 0

    for i in range(q):
        query = input()
        if query == "2":
            calc(keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count,
                 keisuu_upper_sum, keisuu_upper_count, teisuu)

        else:
            _, a, b = [int(i) for i in query.split()]
            teisuu += b

            if a < keisuu_lower_max:
                keisuu_lower, a, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count \
                    = lowerpush(keisuu_lower, a, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count)

            elif a > keisuu_upper_min:
                keisuu_upper, a, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count \
                    = upperpush(keisuu_upper, a, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count)

            elif keisuu_lower_count == keisuu_upper_count:
                keisuu_lower, a, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count \
                    = lowerpush(keisuu_lower, a, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count)

            else:
                keisuu_upper, a, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count \
                    = upperpush(keisuu_upper, a, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count)

            if keisuu_lower_count > keisuu_upper_count + 1:
                keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count, keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count \
                    = from_lower_to_upper(keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count,
                                          keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count)

            elif keisuu_lower_count < keisuu_upper_count:
                keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count, keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count \
                    = from_upper_to_lower(keisuu_lower, keisuu_lower_max, keisuu_lower_sum, keisuu_lower_count,
                                          keisuu_upper, keisuu_upper_min, keisuu_upper_sum, keisuu_upper_count)


main()

Submission status: Accepted

Solution code:
import heapq

Q = int(input())
ans = 0

L = []
R = []

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        l = heapq.heappushpop(L, -q[1])
        r = heapq.heappushpop(R, q[1])
        heapq.heappush(L, -r)
        heapq.heappush(R, -l)
        ans += abs(l + r) + q[2]
    else:
        print(-L[0], ans)

Submission status: Accepted

Solution code:
import heapq
Q = int(input())
INF = 2 * (10 ** 9)
a1, a2 = [INF], [INF]
asum1 = 0
asum2 = 0
bsum = 0
for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 3:
        break
    if query[0] == 1:
        a, b = query[1:]
        bsum += b
        if len(a1) == len(a2):
            if -a1[0] > a:
                asum1 += a
                heapq.heappush(a1, -a)
            else:
                asum2 += a
                heapq.heappush(a2, a)
                asum1 += a2[0]
                asum2 -= a2[0]
                heapq.heappush(a1, -heapq.heappop(a2))
        else:
            if a2[0] < a:
                asum2 += a
                heapq.heappush(a2, a)
            else:
                asum1 += a
                heapq.heappush(a1, -a)
                asum2 += -a1[0]
                asum1 -= -a1[0]
                heapq.heappush(a2, -heapq.heappop(a1))
    else:
        m = -a1[0]
        print(m, m * (len(a1) - 1) -
              asum1 + asum2 - m * (len(a2) - 1) + bsum)