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
import time
import heapq

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    import bisect
    q = int(input())
    left = PriorityQueue([-INF], desc=True)
    right = PriorityQueue([INF])
    const = 0
    cur_f = 0
    length = 0

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            length += 1
            new_a = val[1]
            const += val[2]
            l = left.top()
            r = right.top()
            cur_x = l
            if length % 2 == 1:
                if new_a < l:
                    right.push(left.top())
                    left.push(new_a)
                    cur_f += abs(l - new_a)
                elif new_a <= r:
                    left.push(new_a)
                    right.push(new_a)
                else:
                    left.push(right.top())
                    right.push(new_a)
                    cur_f += abs(r - new_a)
            else:
                if new_a < l:
                    left.pop()
                    left.push(new_a)
                    cur_f += abs(l - new_a)
                else:
                    right.pop()
                    right.push(new_a)
                    cur_f += abs(r - new_a)
        else:
            print(left.top(), cur_f + const)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    Q=int(input())
    Query=[]
    unique_a=set()
    for _ in range(Q):
        q=tuple(map(int,input().split()))
        if q[0]==1:
            unique_a.add(q[1])
            Query.append(q)
        else:
            Query.append((q[0],0,0))
    unique_a=list(unique_a)
    unique_a.sort()
    d={x:i for i,x in enumerate(unique_a)}
    b0=BIT(len(unique_a))
    b1=BIT(len(unique_a))
    sum_b=0
    sum_a=0
    c=0
    for i,(q,a,b) in enumerate(Query,1):
        if q==1:
            b0.add(d[a],1)
            b1.add(d[a],a)
            c+=1
            sum_a+=a
            sum_b+=b
        else:
            index,_=b0.lower_bound(-(-c//2))
            x=unique_a[index]
            tmp=b1.sum(index)
            z=b0.sum(index)
            y=(z*2-c)*x-tmp*2+sum_a+sum_b
            print(x,y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign

q = int(input())
queries = [tuple(map(int, input().split())) for i in range(q)]
INF = 10 ** 12
small = Heapq([-INF],desc=True)
large = Heapq([INF])
fx_min = queries[0][2]
median = queries[0][1]
k = 0
for query in queries[1:]:
  if query[0] == 1:
    k += 1
    a,b = query[1],query[2]
    fx_min += abs(median-a) + b
    small_max, large_min = small.top(), large.top()
    if k % 2: 
      if (a <= median):
        small.push(a)
        large.push(median)
        median = small.top()
      else:
        small.push(median)
        large.push(a)
    else:
      if (a <= small_max):
        small.pop()
        small.push(a)
      elif (small_max < a <= large_min):
        fx_min -= abs(median-a)
        median = a
      else:
        large.push(a)
        newmed = large.pop()
        fx_min -= abs(median-newmed)
        median = newmed 
  else:
    print(median,fx_min)

Submission status: Accepted

Solution code:
import heapq
q=int(input())
L=[]
R=[]
heapq.heapify(L)
heapq.heapify(R)
fx=0
for i in range(q):
  Q=list(map(int,input().split()))
  if Q[0]==1:
    a,b=Q[1],Q[2]
    heapq.heappush(L,-a)
    heapq.heappush(R,a)
    l=-heapq.heappop(L)
    r=heapq.heappop(R)
    if l==a and r==a:
      heapq.heappush(L,-l)
      heapq.heappush(R,r)
    else:
      fx+=abs(r-l)
      heapq.heappush(L,-r)
      heapq.heappush(R,l)
    x=-L[0]
    fx+=b
  else:
    print(x,fx)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
Q = int(input())
query = []
sumL, sumR = [], []
ans = 0
for _ in range(Q):
    a = list(map(int, input().split()))
    if a[0]==1:
        ans += a[2]
        if len(sumL)==0 or a[1] <= -sumL[0]:
            heappush(sumL, -a[1])
            ans += -sumL[0] - a[1]
        else:
            heappush(sumR, a[1])
            ans += sumL[0] + a[1]
    
        if len(sumR) > len(sumL):
            ans -= sumR[0] + sumL[0]
            heappush(sumL, -heappop(sumR))
            
        elif len(sumL) - len(sumR) >= 2:
            heappush(sumR, -heappop(sumL))

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

Submission status: Accepted

Solution code:
# F - Absolute Minima
import heapq

n = int(input())

hq1 = []
hq2 = []
ans = 0

for _ in range(n):
    q = list(map(int, input().split()))
    if q[0]==1:
        heapq.heappush(hq1, q[1]*-1)
        heapq.heappush(hq2, q[1])
        hq1max = heapq.heappop(hq1)*-1
        hq2min = heapq.heappop(hq2)
        heapq.heappush(hq1, hq2min*-1)      
        heapq.heappush(hq2, hq1max)
        ans += abs(hq1max-hq2min) + q[2]        
    if q[0]==2:
        hq1max = heapq.heappop(hq1)*-1
        heapq.heappush(hq1, hq1max*-1)          
        print(hq1max, ans)

Submission status: Accepted

Solution code:
def main():
    from heapq import heappop, heappush
    import sys
    input = sys.stdin.readline

    Q = int(input())

    left = []
    right = []
    sum_l = 0
    sum_r = 0
    cnt = 0
    b = 0
    for _ in range(Q):
        query = map(int, input().split())
        t = next(query)
        if t == 1:
            x, b_ = query
            b += b_
            cnt += 1
            if cnt % 2 == 0:
                heappush(left, -x)
                sum_l += x
                x = -heappop(left)
                sum_l -= x
                heappush(right, x)
                sum_r += x
            else:
                heappush(right, x)
                sum_r += x
                x = heappop(right)
                sum_r -= x
                heappush(left, -x)
                sum_l += x
        else:
            x = -left[0]
            ans = b + sum_r - sum_l + x * (cnt % 2)
            print(x, ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

Q=int(input())
ques=[[] for i in range(0,Q)]
value=set([])
for i in range(0,Q):
    ques[i]=list(map(int,input().split()))
    if ques[i][0]==1:
        value.add(ques[i][1])

value=list(value)
value.sort()
n=len(value)
dic={}
for i in range(n):
    dic[value[i]]=0
    dic[value[i]]=i

#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele =0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

index=dic[ques[0][1]]
update(index,1)
minx=ques[0][1]
minf=0
B=ques[0][2]
count=1
for i in range(1,Q):
    if ques[i][0]==2:
        print(minx,minf+B)
    else:
        a=ques[i][1]
        b=ques[i][2]
        index=dic[a]
        count+=1
        B+=b
        minf+=abs(a-minx)
        update(index,seg[index+num-1]+1)
        start=0
        end=n-1
        while end-start>1:
            test=(end+start)//2
            if query(0,test+1)>=(count+1)//2:
                end=test
            else:
                start=test

        if query(0,start+1)>=(count+1)//2:
            t=start
        else:
            t=end

        if value[t]>minx:
            if count%2==1:
                minf-=value[t]-minx
                minx=value[t]
            else:
                minf-=2*(value[t]-minx)
                minx=value[t]
        elif minx>value[t]:
            if count%2==1:
                minf-=value[t]-minx
                minx=value[t]
            else:
                minx=value[t]

Submission status: Accepted

Solution code:
q = int(input())
ans = [0, 0]
import heapq
p1 = []
p2 = []
heapq.heapify(p1)
heapq.heapify(p2)
sum_b = 0
sum_p1 = 0
sum_p2 = 0
for _ in range(q):
    ql = list(map(int,input().split()))
    if ql[0] == 2:
        if len(p1) == len(p2):
            print(-p2[0], sum_p1 - len(p1) * -p2[0] + len(p2) * -p2[0] - sum_p2 + sum_b)
        else:
            print(p1[0], sum_p1 - len(p1) * p1[0] + len(p2) * p1[0] - sum_p2 + sum_b)
    else:
        sum_b += ql[2]
        if len(p1) == 0:
            heapq.heappush(p1, ql[1])
            sum_p1 += ql[1]
        elif p1[0] <= ql[1]:
            heapq.heappush(p1, ql[1])
            sum_p1 += ql[1]
        else:
            heapq.heappush(p2, -ql[1])
            sum_p2 += ql[1]
        if len(p1) < len(p2):
            k = heapq.heappop(p2)
            heapq.heappush(p1, -k)
            sum_p2 += k
            sum_p1 -= k
        if len(p1) - 1 > len(p2):
            k = heapq.heappop(p1)
            heapq.heappush(p2, -k)
            sum_p1 -= k
            sum_p2 += k

Submission status: Accepted

Solution code:
Q = int(input())
qs = [input().split() for i in range(Q)]

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

    def size(self):
        return len(self.hq)

lq = Heapq([], True)
rq = Heapq([], False)

ofs = 0
for q in qs:
    if q[0] == '2':
        print(lq.top(), ofs)
        continue
    _,a,b, = q
    a,b = int(a),int(b)
    ofs += b
    lq.push(a)
    rq.push(a)
    if lq.top() > rq.top():
        l,r = lq.pop(), rq.pop()
        ofs += abs(l-r)
        lq.push(r)
        rq.push(l)

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(-1,0),(0,1),(0,-1)]

def main():
    sa = sb = 0
    hp1 = []
    hp2 = []
    m = None
    for _ in range(II()):
        ab=input().split()
        if ab[0]=="1":
            a,b=int(ab[1]),int(ab[2])
            sb+=b
            heappush(hp1,-a)
            heappush(hp2,a)
            while -hp1[0]>hp2[0]:
                heappush(hp1,-heappop(hp2))
                heappush(hp2,-heappop(hp1))
            if m==None:
                m=a
                continue
            if -hp1[0]>m:
                d=-hp1[0]-m
                sa+=(len(hp1)-1)//2*d-(len(hp2)+1)//2*d
            if -hp1[0]<m:
                d=hp1[0]+m
                sa+=-(len(hp1))//2*d+(len(hp2))//2*d
            sa += abs(m - a)
            m=-hp1[0]
        else:
            print(m,sa+sb)

main()

Submission status: Accepted

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

Q = int(input())
small = []
large = []
const = 0
total = 0
s = 0
n = 0
m = 0
for _ in range(Q):
    q, *nums = map(int, input().split())
    if q == 1:
        n += 1
        a, b = nums
        total += a
        const += b
        if n % 2 == 0:
            if a > large[0]:
                a = heappushpop(large, a)
            heappush(small, -a)
            m = -small[0]
            s += a
        else:
            if small and a < -small[0]:
                s += a
                a = -heappushpop(small, -a)
                s -= a
            heappush(large, a)
            m = large[0]
    else:
        ans = const + total - 2*s
        if n % 2 == 1:
            ans -= m
        print(m, ans)

Submission status: Accepted

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

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

anss = []
PQL, PQR = [], []
sumL = sumR = 0
numL = numR = 0
sumB = 0
for query in querys:
    if query[0] == 1:  # 更新
        a, b = query[1:]
        sumB += b
        if numL == 0:
            heappush(PQL, -a)
            sumL += a
            numL += 1
        elif numL == numR:
            if a <= -PQL[0]:
                heappush(PQL, -a)
                sumL += a
                numL += 1
            else:
                heappush(PQR, a)
                c = heappop(PQR)
                sumR += a-c
                heappush(PQL, -c)
                sumL += c
                numL += 1
        else:
            if a < -PQL[0]:
                heappush(PQL, -a)
                c = -heappop(PQL)
                sumL += a-c
                heappush(PQR, c)
                sumR += c
                numR += 1
            else:
                heappush(PQR, a)
                sumR += a
                numR += 1

    else:  # 求値
        x = -PQL[0]
        fx = numL*x - sumL + sumR - numR*x + sumB
        anss.append((x, fx))

print('\n'.join(map(lambda x: str(x[0])+' '+str(x[1]), anss)))

Submission status: Accepted

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

def main():
  less = []
  greater = []
  s = 0
  sum_ = 0
  q = int(input())
  def query(n):
    nonlocal s, sum_
    if n[0] == "1":
      c, a, b = map(int, n.split())
      s += b
      if len(less) == len(greater):
        if not greater or a <= greater[0]:
          heapq.heappush(less, -a)
          sum_ -= a
        else:
          r = heapq.heappushpop(greater, a)
          heapq.heappush(less, -r)
          sum_ += a - 2*r
      else:
        if a >= -less[0]:
          heapq.heappush(greater, a)
          sum_ += a
        else:
          r = -heapq.heappushpop(less, -a)
          heapq.heappush(greater, r)
          sum_ += 2*r - a
    else:
      res = sum_
      if len(less) > len(greater):
        res -= less[0]
      res += s
      print(-less[0], res)

  for _ in range(q):
    k = input()
    query(k)
    
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
"""
言い換えると次のことをすればよい
初期値をl = [], s = 0 として
'1 a b': lにaを追加、sにbを足す
'2': 中央値のインデックスより大きい要素の和-～～より小さい要素の和+sを出力
(要素が仮に昇順にソートされているなら、要素数をkとして、
sum(l[(k+1)//2:]) - sum(l[:k//2]) + s　を出力、xとしてはl[(k-1)//2]を出力
"""
import heapq

less = []
greater = []
s = 0
sum_ = 0
q = int(input())
def query(n):
  global s, sum_
  if n[0] == "1":
    c, a, b = map(int, n.split())
    s += b
    if len(less) == len(greater):
      if not greater or a <= greater[0]:
        heapq.heappush(less, -a)
        sum_ -= a
      else:
        r = heapq.heappushpop(greater, a)
        heapq.heappush(less, -r)
        sum_ += a - 2*r
    else:
      if a >= -less[0]:
        heapq.heappush(greater, a)
        sum_ += a
      else:
        r = -heapq.heappushpop(less, -a)
        heapq.heappush(greater, r)
        sum_ += 2*r - a
  else:
    res = sum_
    if len(less) > len(greater):
      res -= less[0]
    res += s
    print(-less[0], res)
    
for _ in range(q):
  k = input()
  query(k)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

q = int(input())

# PQ1に小さい方→PQ1で欲しいのは最大値→負の値でpush
# PQ2に大きい方→PQ2で欲しいのは最小値→そのままpush
# sizeが同じ時はPQ1に入れるようにしておけば常にクエリで取り出すのはPQ1
PQ1 = []
pqsize1 = 0
PQ2 = []
pqsize2 = 0
seppen = 0
a_sum_small = 0
a_sum_big = 0
b_sum = 0
for _ in range(q):
    a = input()
    if a[0] == "1":
        p, q, r = map(int, a.split())
        b_sum += r
        if pqsize1 == 0:  # 初回用
            heappush(PQ1, -q)
            pqsize1 += 1
            a_sum_small += q
        elif pqsize2 == 0:  # 2回め用
            temp = heappop(PQ1)
            temp *= -1
            a_sum_small = 0
            num_list = [temp, q]
            num_list.sort()
            heappush(PQ1, -num_list[0])
            a_sum_small += num_list[0]
            heappush(PQ2, num_list[1])
            a_sum_big += num_list[1]
            pqsize2 += 1
        else:  # それ以後
            # smaller, biggerとqの大小で3パターン
            smaller = heappop(PQ1)
            smaller *= -1
            a_sum_small -= smaller
            bigger = heappop(PQ2)
            a_sum_big -= bigger
            num_list = [smaller, bigger, q]
            num_list.sort()
            x, y, z = num_list
            if pqsize2 < pqsize1:
                heappush(PQ1, -x)
                heappush(PQ2, y)
                heappush(PQ2, z)
                pqsize2 += 1
                a_sum_small += x
                a_sum_big += y + z
            else:
                heappush(PQ1, -x)
                heappush(PQ1, -y)
                heappush(PQ2, z)
                pqsize1 += 1
                a_sum_small += x + y
                a_sum_big += z
    else:
        res = 0
        res += b_sum
        chuo = heappop(PQ1)
        chuo *= -1
        res += pqsize1 * chuo - a_sum_small
        res += a_sum_big - pqsize2 * chuo
        heappush(PQ1, -chuo)
        print(chuo, res)

Submission status: Accepted

Solution code:
q = int(input())

import sys
input = sys.stdin.readline
# ヒープキュー（最小値・最大値の取得）
from heapq import heappop,heappush
left = []
right = []

lsum = 0
rsum = 0
q1_num = 0
b = 0
for _ in range(q):
    qs = tuple(map(int, input().split()))
    if(qs[0]==1):
        b += qs[2]
        if(q1_num == 0):
            heappush(left, qs[1] * -1)
            lsum += qs[1]
            q1_num += 1
            continue
        elif(q1_num%2==1):
            tmp = heappop(left) * -1
            lsum -= tmp

        else:
            tmp = heappop(right)
            rsum -= tmp
        less =  min(tmp, qs[1])
        more =  max(tmp, qs[1])
        heappush(left, less * -1)
        heappush(right, more)
        lsum += less
        rsum += more
        q1_num += 1

    else:
        num = rsum - lsum + b
        tmp = heappop(left) * -1
        if(q1_num%2==1):
            num += tmp
        heappush(left, tmp * -1)
        print(' '.join(map(str, [tmp, num])))

Submission status: Accepted

Solution code:
q = int(input())

import sys
input = sys.stdin.readline
# ヒープキュー（最小値・最大値の取得）
from heapq import heappop,heappush
left = []
right = []

lsum = 0
rsum = 0
q1_num = 0
b = 0
for _ in range(q):
    qs = tuple(map(int, input().split()))
    if(qs[0]==1):
        b += qs[2]
        if(q1_num == 0):
            heappush(left, qs[1] * -1)
            lsum += qs[1]
            q1_num += 1
            continue
        elif(q1_num%2==1):
            tmp = heappop(left) * -1
            lsum -= tmp

        else:
            tmp = heappop(right)
            rsum -= tmp
        less =  min(tmp, qs[1])
        more =  max(tmp, qs[1])
        heappush(left, less * -1)
        heappush(right, more)
        lsum += less
        rsum += more
        q1_num += 1

    else:
        num = rsum - lsum + b
        tmp = heappop(left) * -1
        if(q1_num%2==1):
            num += tmp
        heappush(left, tmp * -1)
        print(' '.join(map(str, [tmp, num])))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n = int(input())
INF = 10 ** 10

left = [INF]
right = [INF]
left_sm = 0
right_sm = 0
cnt = 0
b_sm = 0

for _ in range(n):
    q = input()
    #print(left)
    #print(right)
    #print()

    if q[0] == "1":
        _, a, b = map(int, q.split())

        if cnt % 2:
            if a < -left[0]:
                l2r = -heappop(left)
                left_sm -= l2r
                heappush(left, -a)
                left_sm += a
                heappush(right, l2r)
                right_sm += l2r

            else:
                heappush(right, a)
                right_sm += a

        else:
            if a > right[0]:
                r2l = heappop(right)
                right_sm -= r2l
                heappush(left, -r2l)
                left_sm += r2l
                heappush(right, a)
                right_sm += a

            else:
                heappush(left, -a)
                left_sm += a

        b_sm += b
        cnt += 1

    else:
        x = -left[0]
        fx = -left_sm + right_sm + b_sm
        if cnt % 2:
            fx += x
        print(x, fx)

Submission status: Accepted

Solution code:
q=int(input())
from heapq import heappush,heappop,heapify
l=[]
r=[]
sl=0
sr=0
sb=0
for i in range(q):
    Q=input().split()
    if len(Q)==1:
        x=-l[0]
        print(x,x*len(l)-sl+sr-len(r)*x+sb)
        continue
    a,b=int(Q[1]),int(Q[2])
    sb+=b
    if len(l)>len(r):
        heappush(r,a)
        sr+=a
    else:
        heappush(l,-a)
        sl+=a
    try:
        if r[0]<-l[0]:
            x,y=heappop(r),-heappop(l)
            heappush(r,y)
            sr+=y-x
            heappush(l,-x)
            sl+=x-y
    except:
        pass

Submission status: Accepted

Solution code:
q=int(input())
from heapq import heappush,heappop,heapify
l=[]
r=[]
sl=0
sr=0
sb=0
for i in range(q):
    Q=input().split()
    if len(Q)==1:
        x=-l[0]
        print(x,x*len(l)-sl+sr-len(r)*x+sb)
        continue
    a,b=int(Q[1]),int(Q[2])
    sb+=b
    if len(l)>len(r):
        heappush(r,a)
        sr+=a
    else:
        heappush(l,-a)
        sl+=a
    try:
        if r[0]<-l[0]:
            x,y=heappop(r),-heappop(l)
            heappush(r,y)
            sr+=y-x
            heappush(l,-x)
            sl+=x-y
    except:
        pass

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
  return list(map(int,input().split()))
def m(): #複数文字
  return map(int,input().split())
def onem(): #Nとかの取得
  return int(input())
def s(x): #圧縮
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): #listをスペースごとに分ける
  return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
  return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
  ll = 0
  rr = r
  while True:
    mid = (ll+rr)//2

  if rr == mid:
    return ll
  if (ここに評価入れる):
    rr = mid
  else:
    ll = mid+1
"""

q = onem()

b = 0

AR = []
AL = []

ans = 0



for i in range(q):
  a = l()
  if len(a) == 1:
    if len(AR) == len(AL):
      print(min(AR[0]*-1,AL[0]),ans + b)
    else:
      print(AR[0]*-1,ans + b)

  else:
    b += a[2]
    if AR == []:
      AR.append(-a[1])
    else:
      if len(AR) == len(AL):
        if AL[0] < a[1]:
          ans += a[1]-AL[0]
          hq.heappush(AL,a[1])
          ppp = hq.heappop(AL)
          hq.heappush(AR,ppp*-1)
        else:
          if -1*AR[0] > a[1]:
            ans += (-1*AR[0] - a[1])
          hq.heappush(AR,a[1]*-1)

      else:
        if (AR[0]* -1) > a[1]:
          ans += (-1*AR[0] - a[1])
          hq.heappush(AR,a[1]*-1)
          ppp = hq.heappop(AR)*-1
          hq.heappush(AL,ppp)
        else:
          ans += (AR[0] + a[1])
          hq.heappush(AL,a[1])

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
l,r=[],[]
ans=0
for _ in range(int(input())):
	a=list(map(int,input().split()))
	if a[0]==1:
		_,ia,ib=a
		heappush(l,-ia)
		heappush(r,ia)
		ll=heappop(l)
		rr=heappop(r)
		heappush(l,-rr)
		heappush(r,-ll)
		ans+=ib+abs(ll+rr)
	else:print(-l[0],ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    Q = int(input())
    hs, hl = [], []
    ss, sl = 0, 0
    B = 0
    for _ in range(Q):
        q = input()
        if q == '2':
            x = -hs[0]
            print(x, x * (len(hs) - len(hl)) + sl - ss + B)
            continue
        _, a, b = map(int, q.split())
        B += b
        if hl and a >= hl[0]:
            heapq.heappush(hl, a)
            sl += a
        else:
            heapq.heappush(hs, -a)
            ss += a
        if len(hl) > len(hs):
            while len(hl) > len(hs):
                a = heapq.heappop(hl)
                sl -= a
                heapq.heappush(hs, -a)
                ss += a
        else:
            while len(hs) - len(hl) > 1:
                a = -heapq.heappop(hs)
                ss -= a
                heapq.heappush(hl, a)
                sl += a

main()

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# library
# -------------------------------------------------------------



# -------------------------------------------------------------
# main
# -------------------------------------------------------------
import heapq

L,R = [10**15],[10**15]
lenL,lenR = 1,1
sumL,sumR = 0,0
y = 0

Q = int(input())
for i in range(Q):
    query = list(map(int,input().split()))
    if len(query) == 1:
        x = -L[0]
        f = sumR - sumL + y
        if lenL != lenR:
            f += x
        print("{} {}".format(x, f))
    else:
        q,a,b = query
        y += b
        if lenL > lenR:
            sumL += a
            a = -heapq.heappushpop(L, -a)
            sumL -= a
            heapq.heappush(R, a)
            sumR += a
            lenR += 1
        else:
            sumR += a
            a = heapq.heappushpop(R, a)
            sumR -= a
            heapq.heappush(L, -a)
            sumL += a
            lenL += 1

Submission status: Accepted

Solution code:
import heapq

r = []
l = []
lsum = 0
rsum = 0
y = 0
cnt = 0
Q = int(input())
for _ in range(Q):
    row = input()
    if row == '2':
        x = -heapq.heappop(l)
        print(x, y + rsum - lsum + (cnt%2)*x)
        heapq.heappush(l,-x)
    else:
        row = list(map(int, row.split()))
        a = row[1]
        y += row[2]
        if cnt % 2 == 0:
            heapq.heappush(r,a)
            rsum += a
            _a = heapq.heappop(r)
            rsum -= _a
            heapq.heappush(l,-_a)
            lsum += _a
        else:
            heapq.heappush(l,-a)
            lsum += a
            _a = -heapq.heappop(l)
            lsum -= _a
            heapq.heappush(r,_a)
            rsum += _a
        cnt += 1