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 itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class DammyMap:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.size)
    
    def count(self, i):
        #i(Bの元)以下の個数を取得
        i = self.comp[i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        #iをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        # v番目の値を取得
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddと併用
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, i):
        #i(Bの元)以下のsumを取得
        i = self.comp[i]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, v):
        #v番目までのsumを取得
        x = self.get(v)
        return self.countsum(x) - x*(self.count(x) - v)

Q = int(input())

sumi = 0
geta = 0
k = 0
Query = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]
A = [q[1] for q in Query if len(q) == 3]

T = DammyMap([], A, issum = True)
for q in Query:
    if q[0] == 1:
        k += 1
        geta += q[2]
        a = q[1]
        sumi += a
        T.add(a, 1)
        T.addsum(a, 1)
    else:
        med = T.get(-(-k//2))
        smallsum = T.getsum(-(-k//2))
        print(med, geta + (k%2)*med + sumi - 2*smallsum)

Submission status: Accepted

Solution code:
from heapq import*
L,R=[],[]
B=t=0
Q,*E=open(0)
for e in E:
	if' 'in e:_,a,b=map(int,e.split());t=1-t;a*=2*t-1;c=heappushpop([L,R][t],a);heappush([R,L][t],-c);B+=b+a-c-c
	else:print(-L[0],B-L[0]*t)

Submission status: Accepted

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


# 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():
    Q = int(input())
    sum_b = 0
    sum_al = 0
    sum_ar = 0
    hl = []
    hr = []
    for _ in range(Q):
        buf = input()
        if buf[0] == '1':
            _, a, b = map(int, buf.split())
            sum_b += b
            if len(hl) == 0:
                heapq.heappush(hl, -a)
                sum_al += a
                continue
            if len(hr) == 0:
                heapq.heappush(hr, a)
                sum_ar += a
                if -hl[0] > hr[0]:
                    hl[0], hr[0] = -hr[0], -hl[0]
                    sum_al, sum_ar = sum_ar, sum_al
                continue

            if a < -hl[0]:
                heapq.heappush(hl, -a)
                sum_al += a
            elif a > hr[0]:
                heapq.heappush(hr, a)
                sum_ar += a
            else:
                #if len(hl) <= len(hr):
                heapq.heappush(hl, -a)
                sum_al += a
                #else:
                #    heapq.heappush(hr, a)

            while len(hr) > len(hl):
                tmp = heapq.heappop(hr)
                sum_ar -= tmp
                heapq.heappush(hl, -tmp)
                sum_al += tmp
            while len(hl) > len(hr)+1:
                tmp = heapq.heappop(hl)
                sum_al -= -tmp
                heapq.heappush(hr, -tmp)
                sum_ar += -tmp

        else:
            tmp_al = -hl[0]*len(hl)-sum_al if len(hl) != 0 else 0
            tmp_ar = sum_ar-(-hl[0])*len(hr) if len(hl) != 0 else 0
            #print(hl, sum_al, hr, sum_ar)
            print(-hl[0], tmp_al+tmp_ar+sum_b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush as hp, heappushpop as hppp
import sys
Q = int(input())

sumis = 0
sumib = 0
S = []
B = []

geta = 0
k = 0
med = 0

for _ in range(Q):
    #q = input().split()
    q = sys.stdin.readline().split()
    if q[0] == '1':
        k += 1
        m = int(q[1])
        geta += int(q[2])
        if k % 2 == 1:
            if med < m:
                x = hppp(B, m)
                sumib += m - x
                hp(S, -x)
                sumis += x
            else:
                hp(S, -m)
                sumis += m
        else:
            if med < m:
                hp(B, m)
                sumib += m
            else:
                x = -hppp(S, -m)
                sumis += m - x
                hp(B, x)
                sumib += x
        med = -S[0]
        
    else:
        print(med, geta + med*(k%2) - sumis + sumib)

Submission status: Accepted

Solution code:
import heapq as hq
Q = int(input())
minval = 0
argminval = -(10**9)
#aを大きい方と小さい方に分けて最小ヒープで管理(Lは最大が欲しいので-1掛けておく)
L, R = [10**9], [10**9]
lenL, lenR = 0, 0

for _ in range(Q):
    qi = list(map(int, input().split()))
    if qi[0] == 1:
        ai, bi = qi[1], qi[2]
        LC, RC = -1*L[0], R[0] #左右それぞれで中央に一番近いもの
        if lenL == lenR:
            if ai < RC:
                #Lにaiを追加
                hq.heappush(L, -1*ai)
            else:
                #RCをLに移動, Rにaiを追加
                hq.heappop(R)
                hq.heappush(L, -1*RC)
                hq.heappush(R, ai)
            lenL += 1
            #新しいargminで最小値更新
            argminval = -1*L[0]
            minval += abs(argminval - ai) + bi
        else:
            if ai < LC:
                #LCをRに移動, Lにaiを追加
                hq.heappop(L)
                hq.heappush(L, -1*ai)
                hq.heappush(R, LC)
            else:
                #Rにaiを追加
                hq.heappush(R, ai)
            lenR += 1
            #古いargminで最小値更新
            minval += abs(argminval - ai) + bi
            argminval = -1*L[0]
    else:
        print("{} {}".format(argminval, minval))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue May 28 22:22:21 2019

@author: Yamazaki Kenichi
"""
import heapq

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
Al,Ar = [-(-(10**9+1))],[10**9+1]
d, a, b = map(int,Q2[0].split())
heapq.heappush(Al,-a)
B = b

for i in range(1,Q):
    if Q2[i][0] == '1':
#        intput
        d, a, b = map(int,Q2[i].split())
        if len(Al) == len(Ar):
            if a < Ar[0]:
                heapq.heappush(Al,-a)
            else:
                heapq.heappush(Ar,a)
                heapq.heappush(Al,-(heapq.heappop(Ar)))
            C = abs(a - (-Al[0]))
        else:
            C = abs(a - (-Al[0]))
            if a < Ar[0]:
                heapq.heappush(Al,-a)
                heapq.heappush(Ar,-(heapq.heappop(Al)))
            else:
                heapq.heappush(Ar,a)
        B += (b + C)
#        print(Al,Ar,a,B,b)
    else:
#        output
        ans.append([(-Al[0]),B])

for c in ans:
    print(' '.join(map(str,c)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue May 28 22:22:21 2019

@author: Yamazaki Kenichi
"""
import heapq

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
Al,Ar = [-(-(10**9+1))],[10**9+1]
B = 0
flg = False
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split())
        if not flg:
            heapq.heappush(Al,-a)
            B += b
            flg = True
            continue
        
#        C = abs(a - (-Al[0]))
        if len(Al) == len(Ar):
            if a < Ar[0]:
#                C = abs(a - (-Al[0]))
                heapq.heappush(Al,-a)
#                C = abs(a - (-Al[0]))
#            elif a < Ar[0]:
#                heapq.heappush(Al,-(heapq.heappop(Ar)))
#                heapq.heappush(Ar,a)
                C = abs(a - (-Al[0]))
            else:
                heapq.heappush(Ar,a)
                heapq.heappush(Al,-(heapq.heappop(Ar)))
                C = abs(a - (-Al[0]))
        else:
            if a < Ar[0]:
                C = abs(a - (-Al[0]))
                heapq.heappush(Al,-a)
                heapq.heappush(Ar,-(heapq.heappop(Al)))
#                C = abs(a - (-Al[0]))
#            elif a < A[]
            else:
                C = abs(a - (-Al[0]))
                heapq.heappush(Ar,a)
#                C = abs(a - (-Al[0]))
        B += (b + C)
#        print(Al,Ar,a,B,b)
    else:
#        output
        ans.append([(-Al[0]),B])
        
for c in ans:
    print(' '.join(map(str,c)))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
Q = int(input())
maxh = []
minh = []
sum1 = sum2 = b = med = 0
for i in range(Q):
  q = list(map(int, input().split()))
  if q[0]==1:
    b += q[2]
    if len(maxh)==0 or q[1]<-maxh[0]:
      heappush(maxh, -q[1])
      sum1 += q[1]
      if len(maxh)>len(minh)+1:
        t = -heappop(maxh)
        heappush(minh, t)
        sum1 -= t
        sum2 += t
    else:
      heappush(minh, q[1])
      sum2 += q[1]
      if len(maxh)<len(minh):
        t = heappop(minh)
        heappush(maxh, -t)
        sum1 += t
        sum2 -= t
    med = -maxh[0]
  else:
    ans = len(maxh)*med-sum1+sum2-len(minh)*med+b
    print(med, ans)

Submission status: Accepted

Solution code:

import heapq as hq

Q = int(input())



low = []
high = []

_,mid,val = map(int,input().split())

for _ in range(Q-1):
    s = input()
    if s[0] == '1':
        _,a,b = map(int,s.split())
        if mid is None:
            if a < -low[0]:
                mid = -hq.heapreplace(low, -a)
            elif a > high[0]:
                mid = hq.heapreplace(high, a)
            else:
                mid = a
            val += abs(mid-a)+b
        else:
            val += abs(mid-a)+b
            x,y = sorted((a,mid))
            hq.heappush(high, y)
            hq.heappush(low, -x)
            mid = None

    else:
        print(-low[0] if mid is None else mid, val)

Submission status: Accepted

Solution code:
import sys, heapq
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
  
def solve():
    Q = int(single_input())
    n, a, b = map(int, line_input())
    left, right = [-a], [a]
    heapq.heapify(left)
    heapq.heapify(right)
    minans =  b
    ans = ""
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            if -1 * left[0] <= a <= right[0]:
                heapq.heappush(left, -a)
                heapq.heappush(right, a)
            elif a < -1 * left[0]:
                minans += (-1 * left[0]) - a
                heapq.heappush(left, -a)
                heapq.heappush(left, -a)
                heapq.heappush(right, -1 * heapq.heappop(left))
            else:
                minans += a - right[0]
                heapq.heappush(left, -1 * heapq.heappop(right))
                heapq.heappush(right, a)
                heapq.heappush(right, a)
        else: ans += str(-1 * left[0]) + " " + str(minans) + "\n"
    print(ans)

    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    Q = int(single_input())
    n, a, b = map(int, line_input())
    left, right = [-a], [a]
    heapq.heapify(left)
    heapq.heapify(right)
    minans =  b
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            if -1 * left[0] <= a <= right[0]:
                heapq.heappush(left, -a)
                heapq.heappush(right, a)
            elif a < -1 * left[0]:
                minans += (-1 * left[0]) - a
                heapq.heappush(left, -a)
                heapq.heappush(left, -a)
                heapq.heappush(right, -1 * heapq.heappop(left))
            else:
                minans += a - right[0]
                heapq.heappush(left, -1 * heapq.heappop(right))
                heapq.heappush(right, a)
                heapq.heappush(right, a)
        else: print(-1 * left[0], minans)

    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    Q = int(single_input())
    n, a, b = map(int, line_input())
    left, right = [-a], [a]
    heapq.heapify(left)
    heapq.heapify(right)
    minans =  b
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            left_upper = -1 * heapq.heappop(left)
            right_lower = heapq.heappop(right)
            if left_upper <= a <= right_lower:
                heapq.heappush(left, -a)
                heapq.heappush(left, -1 * left_upper)
                heapq.heappush(right, a)
                heapq.heappush(right, right_lower)
            elif a < left_upper:
                minans += left_upper - a
                heapq.heappush(left, -a)
                heapq.heappush(left, -a)
                heapq.heappush(right, left_upper)
                heapq.heappush(right, right_lower)
            else:
                minans += a - right_lower
                heapq.heappush(left, -1 * left_upper)
                heapq.heappush(left, -1 * right_lower)
                heapq.heappush(right, a)
                heapq.heappush(right, a)
        else:
            left_lower = -1 * heapq.heappop(left)
            print(left_lower, minans)
            heapq.heappush(left, -1 * left_lower)
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq

Q = int(input())


def update(ans, a, b):
    heapq.heappush(lq, -a)
    heapq.heappush(rq, a)
    lmax, rmin = -lq[0], rq[0]
    ans += b
    if lmax > rmin:
        lmax, rmin = rmin, lmax
        ans += rmin - lmax
        heapq.heappop(lq)
        heapq.heappop(rq)
        heapq.heappush(lq, -lmax)
        heapq.heappush(rq, rmin)
    return ans


def query():
    return str(-lq[0]) + ' ' + str(ans)


lq = []
rq = []
ans = 0

for i in range(Q):
    q = list(map(str, input().split()))
    if len(q) == 1:
        print(query())
    else:
        one, a, b = q
        ans = update(ans, int(a), int(b))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heappushpop

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

ans = 0

heappush(L, -q[0][1])

for i in range(1, n):
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            ans += abs(temp[1] + L[0])
            p = heappushpop(L, - temp[1])
            heappush(R, - p)
        else:
            ans += abs(temp[1] + L[0])
            tl = L[0]
            p = heappushpop(R, temp[1])
            heappush(L, - p)
            if tl != L[0]:
                ans -= abs(tl - L[0])
        b += temp[2]
    else:
        m = - L[0]
        print(m, ans + b)

Submission status: Accepted

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

import heapq
MIN=[]
MAX=[]
ANS=0
SCORE=0

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

    if Q[0]==1:
        ANS+=Q[2]
        heapq.heappush(MIN,Q[1])
        heapq.heappush(MAX,-Q[1])

        if MIN[0]<-MAX[0]:
            x=heapq.heappop(MIN)
            y=-heapq.heappop(MAX)

            SCORE+=(y-x)
            heapq.heappush(MIN,y)
            heapq.heappush(MAX,-x)

    else:
        print(-MAX[0],ANS+SCORE)

Submission status: Accepted

Solution code:
import heapq

Q = int(input())
Query = [input() for _ in range(Q)]

ans = 0

lq = []
rq = []

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        heapq.heappush(lq, -a)
        heapq.heappush(rq, a)

        lmax, rmin = -lq[0], rq[0]
        if lmax > rmin :
            lmax, rmin = rmin, lmax
            ans += rmin - lmax

            heapq.heappop(lq)
            heapq.heappop(rq)
            heapq.heappush(lq, -lmax)
            heapq.heappush(rq, rmin)

        ans += b

    else :
        print(-lq[0], ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    from heapq import heappush, heappushpop, heappop
    Q = I()
    # highはそのままheapq
    high = []
    # lowは一番デカイのを取り出せるように符号逆転して、heapq
    low = []

    _, a, b = MI()
    heappush(low, -a)

    debug = [a]

    # debug用
    def solve(n):
        ans = 0
        for a in debug:
            ans += abs(a - n)

        return B + ans

    B = b
    ans = 0
    cnt = 1
    for _ in range(Q - 1):
        inp = input()
        if inp[0] == "1":
            _, a, b = map(int, inp.split())
            B += b
            debug.append(a)
            cnt += 1

            # 偶数なら答えを更新してから、heapqを更新
            if cnt % 2 == 0:
                ans += abs(-low[0]-a)
                even = True
            else:
                even = False

            # lowに入れるかhighに入れるか
            if a > -low[0]:
                heappush(high, a)
            else:
                heappush(low, -a)

            # 中央値がわかるように平衡化
            if len(low) < len(high):
                heappush(low, -heappop(high))
            elif len(low) > len(high) + 1:
                heappush(high, -heappop(low))

            # 奇数ならheapqを更新してから答えを更新
            if not even:
                ans += abs(-low[0] - a)

        else:
            print(-low[0], ans + B)
            #print(-low[0], solve(-low[0]))
        #print(sorted(debug), low, high, ans)
    # print(sorted(debug))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    from heapq import heappush, heappushpop, heappop
    Q = I()
    high = []
    low = []
    _, a, b = MI()
    debug = [a]

    heappush(low, -a)

    def solve(n):
        ans = 0
        for a in debug:
            ans += abs(a - n)

        return B + ans

    B = b
    ans = 0
    cnt = 1
    for _ in range(Q - 1):
        inp = input()
        if inp[0] == "1":
            q, a, b = map(int, inp.split())
            B += b
            debug.append(a)
            cnt += 1
            if cnt % 2 == 0:
                ans += abs(-low[0]-a)
                even = True
            else:
                even = False

            if a > -low[0]:
                heappush(high, a)
            else:
                heappush(low, -a)

            if len(low) < len(high):
                heappush(low, -heappop(high))
            elif len(low) > len(high) + 1:
                heappush(high, -heappop(low))

            if not even:
                ans += abs(-low[0]-a)
        else:
            print(-low[0], ans + B)
            #print(-low[0], solve(-low[0]))
        #print(sorted(debug), low, high, ans)
    # print(sorted(debug))


if __name__ == '__main__':
    main()


"""    むり
    heap_max = []
    cnt = 1
    _, a, b = MI()
    heappush(h, a)
    heappush(heap_max, -a)
    B = b
    A_list = [a]
    minA = a
    maxA = a

    def solve(n):
        ans = 0
        for a in A_list:
            ans += abs(a - n)

        return B + ans

    ans = 0

    debug = [a]

    for _ in range(Q-1):
        inp = input()
        if inp[0] == "1":
            q, a, b = map(int, inp.split())

            debug.append(a)

            if q == 1:
                cnt += 1
                B += b

                if cnt % 2 == 0:
                    ans += abs(-heap_max[0]-a)
                    heappush(h, a)
                    heappush(heap_max, -a)
                else:
                    poped = heappushpop(h, a)
                    #print(minA, a, maxA)
                    if -poped != a:
                        heappushpop(heap_max, -a)

                    if minA < a < maxA:
                        ans += abs(-heap_max[0] - a)
                        print(-heap_max[0], a)
                        pass
                    else:
                        ans += abs(-heap_max[0] - a)

            minA = min(a, minA)
            maxA = max(a, maxA)
        else:
            if cnt % 2 == 0:
                if cnt >= 3:
                    print(max(-heap_max[1], -heap_max[2]), ans + B)
                    print(solve(max(-heap_max[1], -heap_max[2])))
                else:
                    print(-heap_max[1], ans + B)
                    print(solve(-heap_max[1]))
            else:
                print(-heap_max[0], ans + B)
                print(-heap_max[0], solve(-heap_max[0]))

        print(heap_max)
        print(sorted(debug), sorted(debug)[len(debug)//2])
"""

Submission status: Accepted

Solution code:
import heapq

Q = int(input())
Query = [input() for _ in range(Q)]

ans = 0

lq = []
rq = []

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        heapq.heappush(lq, -a)
        heapq.heappush(rq, a)

        lmax, rmin = -heapq.heappop(lq), heapq.heappop(rq)
        if lmax > rmin :
            lmax, rmin = rmin, lmax
            ans += rmin - lmax

        heapq.heappush(lq, -lmax)
        heapq.heappush(rq, rmin)

        ans += b

    else :
        print(-lq[0], ans)

Submission status: Accepted

Solution code:
def f_absolute_minima(Q, Queries, INF=float('inf')):
    import heapq

    left, right = [], []
    current_ans, current_median = 0, 0
    bias_total = 0
    heapq.heappush(left, INF)
    heapq.heappush(right, INF)
    ans = []

    for query in Queries:
        if query[0] == 1:  # 更新クエリ
            _, a, b = query
            bias_total += b

            # leftからは最大値を、rightからは最小値を取り出したい
            last_left, last_right = -left[0], right[0]
            heapq.heappush(left, -a)
            heapq.heappush(right, a)
            heapq.heappush(left, -heapq.heappop(right))
            heapq.heappush(right, -heapq.heappop(left))
            current_median = -left[0]
            # 区間外。区間の端点との距離のうち、長くない方を足す
            if a < last_left or last_right < a:
                current_ans += min(abs(last_right - a), abs(last_left - a))
        else:  # 求値クエリ
            ans.append((current_median, current_ans + bias_total))
    return '\n'.join(' '.join(map(str, row)) for row in ans)
    # 参考: https://atcoder.jp/contests/abc127/submissions/5656120

Q = int(input())
Queries = [[int(i) for i in input().split()] for j in range(Q)]
print(f_absolute_minima(Q, Queries))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

qn = int(input())

low = []
high = []
ans = 0

for i in range(qn):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        ans += q[2]
        a = q[1]

        # lowは降順に並べたいので-aを入れる
        heappush(low, -a)
        heappush(high, a)
        if -low[0] > high[0]:
            low0 = heappop(low)
            high0 = heappop(high)
            # lowとhighで正負が逆なので注意する
            heappush(low, -high0)
            heappush(high, -low0)
            ans += - low0 - high0

    elif q[0] == 2:
        print(-low[0], ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

qn = int(input())

low = []
high = []
ans = 0

for i in range(qn):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        ans += q[2]
        a = q[1]

        if len(low) >= 1:
            if a < -low[0]:
                ans += -low[0] - a
            elif a > high[0]:
                ans += a - high[0]

        # lowは降順に並べたいので-aを入れる
        heappush(low, -a)
        heappush(high, a)
        if -low[0] > high[0]:
            low0 = heappop(low)
            high0 = heappop(high)
            # lowとhighで正負が逆なので注意する
            heappush(low, -high0)
            heappush(high, -low0)

    elif q[0] == 2:
        print(-low[0], ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

qn = int(input())

low = []
high = []
ans = 0
num = 0

for i in range(qn):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        # update
        ans += q[2]
        a = q[1]
        heappush(low, -a)
        heappush(high, a)
        if -low[0] > high[0]:
            low0 = heappop(low)
            high0 = heappop(high)
            heappush(low, -high0)
            heappush(high, -low0)
            ans += -low0 - high0
    if q[0] == 2:
        print(-low[0], ans)

Submission status: Accepted

Solution code:
import heapq
Q = int(input())
L = []
R = []
ans = []
min = 0
for _ in range(Q):
    q, *c = map(int, input().split())
    if q == 1:
        a, b = c
        min += b
        heapq.heappush(L, -a)
        heapq.heappush(R, a)
        if -L[0] > R[0]:
            x = -heapq.heappop(L)
            y = heapq.heappop(R)
            heapq.heappush(L, -y)
            heapq.heappush(R, x)
            min += abs(x-y)
    else:
        ans.append((-L[0], min))
for x in ans:
    print(*x)

Submission status: Accepted

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

INF = 10 ** 10

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)]

left = []
right = []
a_s = []
current_median = None
heapq.heappush(left, INF)
heapq.heappush(right, INF)
a_current = 0
for query in qs:
    if query[0] == 1:
        _, a, b = query
        a_s.append(a)
        b_all += b

        last_left, last_right = -left[0], right[0]
        heapq.heappush(left, -a)
        heapq.heappush(right, a)
        heapq.heappush(left, -heapq.heappop(right))
        heapq.heappush(right, -heapq.heappop(left))
        current_median = -left[0]
        if last_left <= a and a <= last_right:
            pass
        else:
            # a_current += abs(left[0] + right[0])
            a_current += min(abs(last_right - a), abs(last_left - a))
    else:
        print(current_median, a_current+b_all)

exit(0)