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 heapq
Q = int(input())

# 中央値の左側の値、右側の値を管理する
# heapqとする。rightは最小が興味あるが、leftは最大なので、-1をかけて扱う
left, right = [], []
# 両方のSUMも管理する必要がある。毎回SUMしてたら間に合わん
Lsum, Rsum = 0,0
Lcnt, Rcnt = 0,0
B = 0
for _ in range(Q):
  q = list(map(int, input().split()))
  if len(q) == 1:
    # 2
    # heapqってPeakできないの・・・？
    l = (-1) *left[0]
    #l = (-1) * heapq.heappop(left)
    #heapq.heappush(left,(-1)*l)
    # (l-l1) + (l-l2) + ... + (l-l) + (r-l) + ... + (r1 - l)
    print(l, Rsum//2 - Lsum//2 + B)
    #print(left,right, Lsum, Rsum)
  else:
    # 1
    _,a,b = q
    B += b
    # まず双方にaを突っ込む
    heapq.heappush(left,(-1)*a)
    heapq.heappush(right,a)
    Lsum += a
    Lcnt += 1
    Rsum += a
    Rcnt += 1
    # leftの最大値と、rightの最小値の関係が崩れていたら、交換する
    l = (-1)*left[0]
    r = right[0]
    #l = (-1) * heapq.heappop(left)
    #r = heapq.heappop(right)
    if l>=r:
      Lsum = Lsum - l + r
      Rsum = Rsum - r + l
      l,r = r,l
    _ = heapq.heappop(left)
    _ = heapq.heappop(right)
    heapq.heappush(left,(-1)*l)
    heapq.heappush(right,r)

Submission status: Accepted

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

# 中央値の左側の値、右側の値を管理する
# heapqとする。rightは最小が興味あるが、leftは最大なので、-1をかけて扱う
left, right = [], []
# 両方のSUMも管理する必要がある。毎回SUMしてたら間に合わん
Lsum, Rsum = 0,0
Lcnt, Rcnt = 0,0
B = 0
for _ in range(Q):
  q = list(map(int, input().split()))
  if len(q) == 1:
    # 2
    # heapqってPeakできないの・・・？
    l = (-1) * heapq.heappop(left)
    heapq.heappush(left,(-1)*l)
    # (l-l1) + (l-l2) + ... + (l-l) + (r-l) + ... + (r1 - l)
    print(l, Rsum//2 - Lsum//2 + B)
    #print(left,right, Lsum, Rsum)
  else:
    # 1
    _,a,b = q
    B += b
    # まず双方にaを突っ込む
    heapq.heappush(left,(-1)*a)
    heapq.heappush(right,a)
    Lsum += a
    Lcnt += 1
    Rsum += a
    Rcnt += 1
    # leftの最大値と、rightの最小値の関係が崩れていたら、交換する
    l = (-1) * heapq.heappop(left)
    r = heapq.heappop(right)
    if l>=r:
      Lsum = Lsum - l + r
      Rsum = Rsum - r + l
      l,r = r,l
    heapq.heappush(left,(-1)*l)
    heapq.heappush(right,r)

Submission status: Accepted

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

A_left, A_right = [], []
A_left_sum, A_right_sum = 0, 0
heapq.heapify(A_left)
heapq.heapify(A_right)

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

    if query[0] == 1:
        now = query[1]
        B_sum += query[2]

        l, r = len(A_left), len(A_right)
        if l <= r:
            heapq.heappush(A_right, now)
            A_right_sum += now

            out = heapq.heappop(A_right)
            A_right_sum -= out

            heapq.heappush(A_left, -out)
            A_left_sum += out
        else:
            heapq.heappush(A_left, -now)
            A_left_sum += now

            out = -heapq.heappop(A_left)
            A_left_sum -= out

            heapq.heappush(A_right, out)
            A_right_sum += out
    else:
        m = -A_left[0]
        ans = len(A_left) * m - A_left_sum - len(A_right) * m + A_right_sum + B_sum
        print("{0} {1}".format(m,ans))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

Q = I()

from heapq import heapify,heappop,heappush

s,t = 0,0  # |x-a|たちの和の最小値、bたちの和
left,right = [],[]  # aたちの中で中間値より小さいもの、大きいもの
heapify(left)
heapify(right)
l,r = 0,0  # left,right の長さ
for i in range(Q):
    A = LI()
    if A[0] == 2:
        if l == r:
            x = -heappop(left)
            heappush(left,-x)
        else:
            x = heappop(right)
            heappush(right,x)
        print(*[x,s+t])
    else:
        c,a,b = A
        t += b
        if l == r:
            if l == 0:
                heappush(right,a)
            else:
                x = -heappop(left)
                y = heappop(right)
                if a >= x:
                    heappush(left,-x)
                    heappush(right,y)
                    heappush(right,a)
                    if a >= y:
                        s += a-y
                else:
                    heappush(left,-a)
                    heappush(right,x)
                    heappush(right,y)
                    s += x-a
            r += 1
        else:
            if l == 0:
                y = heappop(right)
                s += abs(y-a)
                if a < y:
                    heappush(left,-a)
                    heappush(right,y)
                else:
                    heappush(left,-y)
                    heappush(right,a)
            else:
                x = -heappop(left)
                y = heappop(right)
                s += abs(y-a)
                if a < y:
                    heappush(left,-x)
                    heappush(left,-a)
                    heappush(right,y)
                else:
                    heappush(left,-x)
                    heappush(left,-y)
                    heappush(right,a)
            l += 1

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n = int(input())
_, a, b = map(int, input().split())
l = []
r = []
med_val = a
sum_l = 0
sum_r = 0
sum_b = b

for _ in range(n-1):
    query = input().split()
    if query[0] == '1':
        _, a, b = map(int, query)
        if len(l) < len(r):
            if a <= med_val:
                heappush(l, -a)
                sum_l += a
            else:
                heappush(l, -med_val)
                sum_l += med_val
                heappush(r, a)
                sum_r += a
                med_val = heappop(r)
                sum_r -= med_val
        else:
            if med_val < a:
                heappush(r, a)
                sum_r += a
            else:
                heappush(r, med_val)
                sum_r += med_val
                heappush(l, -a)
                sum_l += a
                med_val = -heappop(l)
                sum_l -= med_val
        sum_b += b
    else:
        f = len(l) * med_val - sum_l + sum_r - len(r) * med_val + sum_b
        print("{} {}".format(med_val, f))

Submission status: Accepted

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

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


"""
前回の最小区間を覚えておいて，差分で最小値を更新する
"""

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################


    
    inf=10**9+1
    Q=I()
    ssl1 = SquareSkipList(square=2000)
    ssl1.add(-inf)
    ssl2 = SquareSkipList(square=2000)
    ssl2.add(inf)
    
    s1=0#和
    s2=0
    
    q,a,b=MI()
    mx=a#最小値を与えるx
    m=b#最小値
    
    
    for _ in range(Q-1):
        q=LI()
        if q[0]==1:
            a=q[1]
            m+=q[2]
            aa=ssl1.search_lower(inf+1)#下側の最大値
            bb=ssl2.search_higher(-inf-1)#上側の最小値
            # print(a,aa,mx,bb,l1,l2)
            
            #足す動作
            if a<aa:
                ssl1.add(a)
                s1+=a
            elif a>bb:
                ssl2.add(a)
                s2+=a
            else:
                # 常にa<mxとなるようにしておく
                if a>mx:
                    a,mx=mx,a
                
                #とりあえずmxを上側に足しとく
                ssl2.add(mx)
                s2+=mx
                bb=mx
                mx=a
            l1=ssl1.len()
            l2=ssl2.len()

            #帳尻合わせの移動
            if l1>l2:
                ssl2.add(mx)
                s2+=mx
                ssl1.remove(aa)
                s1-=aa
                mx=aa      
            elif l2-l1>=2:
                ssl1.add(mx)
                s1+=mx
                ssl2.remove(bb)
                s2-=bb
                mx=bb

        else:
            temp=m
            l1=ssl1.len() -1
            l2=ssl2.len() -1
            temp+=l1*mx-s1
            temp+=s2-l2*mx
            print(mx,temp)
                    
                
            
            
            
            
        
        
    

main()

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
inf = 10**18
L = [-(-inf)]
R = [inf]
Lsum = 0
Rsum = 0
const = 0


"""
[], []
[x], []
[x], [y]
[x, z], [y]
...
"""

xmed = None

for _ in range(N):
    f, *arg = map(int, input().split())
    if f == 1:
        a, b = arg
        const += b
        if xmed is None:
            xmed = a
            while -L[0] > xmed or xmed > R[0]:
                while xmed < -L[0]:
                    Lsum += xmed
                    xmed = -heapq.heappushpop(L, -xmed)
                    Lsum -= xmed
                while xmed > R[0]:
                    Rsum += xmed
                    xmed = heapq.heappushpop(R, xmed)
                    Rsum -= xmed
        else:
            if a < xmed:
                a, xmed = xmed, a
            heapq.heappush(L, -xmed)
            heapq.heappush(R, a)
            Lsum += xmed
            Rsum += a
            xmed = None
            while -L[0] > R[0]:
                lx = -heapq.heappop(L)
                rx = heapq.heappop(R)
                heapq.heappush(L, -rx)
                heapq.heappush(R, lx)
                Lsum += rx - lx
                Rsum += lx - rx
    else:
        if xmed is None:
            xres = -L[0]
        else:
            xres = xmed
        F = const
        F += Rsum - xres * (len(R) - 1)
        F += xres * (len(L) - 1) - Lsum
        print(xres, F)

Submission status: Accepted

Solution code:
import heapq
import collections

cnt=1
cnts=collections.defaultdict(int)
median=0
left_cnt=0
right_cnt=0
left_sum=0
right_sum=0
left_pos=[]
right_pos=[]
b=0
q=int(input())
initial=list(map(int,input().split()))
median=initial[1]
b+=initial[2]
cnts[median]=1
for _ in range(q-1):
  query=list(map(int,input().split()))
  if query[0]==1:
    cnt+=1
    b+=query[2]
    if query[1]==median:
      cnts[median]+=1
    elif query[1]<median:
      left_cnt+=1
      left_sum+=query[1]
      cnts[query[1]]+=1
      if cnts[query[1]]==1:
        heapq.heappush(left_pos,-query[1])
    elif query[1]>median:
      right_cnt+=1
      right_sum+=query[1]
      cnts[query[1]]+=1
      if cnts[query[1]]==1:
        heapq.heappush(right_pos,query[1])
    if left_cnt+1<=(cnt+1)//2<=left_cnt+cnts[median]:
      continue
    elif left_cnt+1>(cnt+1)//2:
      heapq.heappush(right_pos,median)
      right_cnt+=cnts[median]
      right_sum+=median*cnts[median]
      median=-heapq.heappop(left_pos)
      left_cnt-=cnts[median]
      left_sum-=median*cnts[median]
    elif (cnt+1)//2>left_cnt+cnts[median]:
      heapq.heappush(left_pos,-median)
      left_cnt+=cnts[median]
      left_sum+=median*cnts[median]
      median=heapq.heappop(right_pos)
      right_cnt-=cnts[median]
      right_sum-=median*cnts[median]
  elif query[0]==2:
    value=b
    if left_cnt!=0:
      value+=abs(left_sum-median*left_cnt)
    if right_cnt!=0:
      value+=abs(right_sum-median*right_cnt)
    print(median,value)

Submission status: Accepted

Solution code:
import heapq


def main():
    Q = int(input())
    query_list = [list(map(int, input().split(' '))) for _ in range(Q)]
    # fの最小を与えるxの計算用
    que_left, que_right = [], []  # 最大ヒープと最小ヒープ
    # fの最小値の計算用
    sum_a_cost = 0
    sum_b = 0
    for query in query_list:
        if query[0] == 1:
            a, b = query[1], query[2]
            # fの更新
            if len(que_right) - len(que_left) == 1:
                sum_a_cost += abs(a - que_right[0])
            elif 0 < len(que_left) == len(que_right):
                if a > que_right[0]:
                    sum_a_cost += a - que_right[0]
                elif a < - que_left[0]:
                    sum_a_cost += - que_left[0] - a
            sum_b += b
            # xの更新
            if len(que_right) == 0 or a >= que_right[0]:
                heapq.heappush(que_right, a)
            else:
                # 最大ヒープにするため符号反転
                heapq.heappush(que_left, - a)
            # ヒープのサイズ差が0 or 1になるよう調整
            if len(que_right) - len(que_left) == - 1:
                heapq.heappush(que_right, - heapq.heappop(que_left))
            elif len(que_right) - len(que_left) == 2:
                heapq.heappush(que_left, - heapq.heappop(que_right))
        else:
            x = que_right[0] if len(que_right) - len(que_left) == 1 else (- que_left[0])
            f = sum_a_cost + sum_b
            print('{} {}'.format(x, f))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


class Medians:
    def __init__(self):
        self.left = []
        self.right = []
        self.size_l = 0
        self.size_r = 0
        self.sum_l = 0
        self.sum_r = 0

    def add(self, n):
        if self.size_l > self.size_r:
            t = -self.left[0]
            if n >= t:
                heappush(self.right, n)
                self.sum_r += n
            else:
                heappop(self.left)
                self.sum_l -= t
                heappush(self.left, -n)
                self.sum_l += n
                heappush(self.right, t)
                self.sum_r += t
            self.size_r += 1
        else:
            if not self.size_l:
                heappush(self.left, -n)
                self.sum_l += n
            else:
                t = self.right[0]
                if n <= t:
                    heappush(self.left, -n)
                    self.sum_l += n
                else:
                    heappop(self.right)
                    self.sum_r -= t
                    heappush(self.right, n)
                    self.sum_r += n
                    heappush(self.left, -t)
                    self.sum_l += t
            self.size_l += 1
    
    def get(self):
        return -self.left[0]


def solve():
    Q = int(input())
    s = 0
    med = Medians()
    for _ in range(Q):
        q, *l, = map(int, input().split())
        if q == 1:
            a, b = l
            s += b
            med.add(a)
        else:
            m = med.get()
            d1 = med.size_l - med.size_r
            d2 = med.sum_r - med.sum_l
            print(m, m*d1+d2+s)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


class Medians:
    def __init__(self):
        self.left = []
        self.right = []
        self.size_l = 0
        self.size_r = 0
        self.sum_l = 0
        self.sum_r = 0

    def add(self, n):
        if self.size_l > self.size_r:
            t = -self.left[0]
            if n >= t:
                heappush(self.right, n)
                self.sum_r += n
            else:
                heappop(self.left)
                self.sum_l -= t
                heappush(self.left, -n)
                self.sum_l += n
                heappush(self.right, t)
                self.sum_r += t
            self.size_r += 1
        else:
            if not self.size_l:
                heappush(self.left, -n)
                self.sum_l += n
            else:
                t = self.right[0]
                if n <= t:
                    heappush(self.left, -n)
                    self.sum_l += n
                else:
                    heappop(self.right)
                    self.sum_r -= t
                    heappush(self.right, n)
                    self.sum_r += n
                    heappush(self.left, -t)
                    self.sum_l += t
            self.size_l += 1
    
    def get(self):
        return -self.left[0]


def solve():
    Q = int(input())
    s = 0
    med = Medians()
    for _ in range(Q):
        q, *l, = map(int, input().split())
        if q == 1:
            a, b = l
            s += b
            med.add(a)
        else:
            m = med.get()
            d1 = med.size_l - med.size_r
            d2 = med.sum_r - med.sum_l
            print(m, m*d1+d2+s)


if __name__ == "__main__":
    solve()

    # med = Medians()
    # for i in [4,3,5,1,2,7,9]:
    #     med.add(i)
    #     print(med.get())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    Q = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    low=[]
    high=[]
    s1=s2=0
    btot=0
    for _ in range(Q):
        q=list(map(int, input().split()))
        if q[0]==1:
            a,b=q[1:]
            btot+=b
            if not low:
                heappush(low,-a)
                s1+=a
                continue
            if a>-low[0]:
                heappush(high,a)
                s2+=a
                if len(low)<len(high):
                    a2=heappop(high)
                    heappush(low,-a2)
                    s2-=a2
                    s1+=a2
            else:
                heappush(low,-a)
                s1+=a
                if len(high)+1<len(low):
                    a2=-heappop(low)
                    heappush(high,a2)
                    s1-=a2
                    s2+=a2
        else:
            if len(low)==0:
                print(0)
                continue
            ans=btot
            mid=-low[0]
            ans+=len(low)*mid-s1-len(high)*mid+s2
            print(mid,round(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
qq = int(input())
ans = 0
hq1 = []
hq2 = []
x = 10 ** 10
c = 0
p, q = 0, 0
for _ in range(qq):
    que = list(map(int, input().split()))
    if que[0] == 1:
        a, b = que[1:]
        ans += b
        if c % 2 == 0:
            if a <= x:
                heapq.heappush(hq1, -a)
                p += a
            else:
                heapq.heappush(hq2, a)
                q += a
                y = heapq.heappop(hq2)
                q -= y
                heapq.heappush(hq1, -y)
                p += y
        else:
            if a <= x:
                heapq.heappush(hq1, -a)
                p += a
                y = -heapq.heappop(hq1)
                p -= y
                heapq.heappush(hq2, y)
                q += y
            else:
                heapq.heappush(hq2, a)
                q += a
        x = -hq1[0]
        c += 1
    else:
        print(x, q - len(hq2) * x + len(hq1) * x - p + ans)

Submission status: Accepted

Solution code:
# absolute minima
import heapq
Q = int(input())
que = [tuple(map(int, input().split())) for _ in range(Q)]

const_term = 0
smaller = []  # 中央値以下の値を管理する((x+1)/2 以下)
smaller_sum = 0
bigger = []  # 中央値より大の値を管理する((x+1)/2 より大きい)
bigger_sum = 0
heapq.heapify(smaller)
heapq.heapify(bigger)
add_count = 0  # 何回要素として加えられたか
for x in que:
    status = x[0]
    if status == 1:
        # 更新クエリ
        add_value, add_const = x[1], x[2]
        const_term += add_const
        if add_count == 0:
            heapq.heappush(smaller, -add_value)
            smaller_sum += add_value
            add_count += 1
            continue
        elif add_count % 2 == 0:
            k_term = smaller[0]*(-1)
            k_1_term = bigger[0]
            if k_1_term >= add_value:
                heapq.heappush(smaller, add_value*(-1))
                smaller_sum += add_value
                add_count += 1
                continue
            elif k_1_term < add_value:
                x = heapq.heappop(bigger)
                bigger_sum -= x
                heapq.heappush(smaller, -x)
                smaller_sum += x
                heapq.heappush(bigger, add_value)
                bigger_sum += add_value
                add_count += 1
                continue
        else:
            if add_count == 1:
                k_term = smaller[0]*(-1)
                add_count += 1
                if k_term <= add_value:
                    heapq.heappush(bigger, add_value)
                    bigger_sum += add_value
                    continue
                elif k_term > add_value:
                    x = heapq.heappop(smaller)*(-1)
                    smaller_sum -= x
                    heapq.heappush(bigger, x)
                    bigger_sum += x
                    heapq.heappush(smaller, -add_value)
                    smaller_sum += add_value
                    continue
            else:
                add_count += 1
                k_1_term = heapq.heappop(smaller)*(-1)
                smaller_sum -= k_1_term
                M = max(k_1_term, add_value)
                m = min(k_1_term, add_value)
                heapq.heappush(bigger, M)
                bigger_sum += M
                heapq.heappush(smaller, -m)
                smaller_sum += m
                continue

    else:
        # 回答クエリ
        X = smaller[0]*(-1)
        P = (add_count+1)//2
        print(X, bigger_sum-smaller_sum+X*(2*P-add_count)+const_term)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify

INF = float("inf")


def main():
    Q = int(input())
    bottom = [INF]                 # 最大ヒープ
    top = [INF]               # 最小ヒープ
    bottom_total = 0
    top_total = 0

    btot = 0
    for i in range(Q):
        q = input()
        if q[0] == "1":
            _, a, b = map(int, q.split())
            # print("a, b", a, b)
            btot += b
            if top[0] < a:
                # 必ずtopに加えるパターン
                heappush(top, a)
                top_total += a
            elif -bottom[0] < a:
                # どちらでも良いパターン
                heappush(bottom, -a)
                bottom_total += a
            else:
                # 必ずbottomに加えるパターン
                heappush(bottom, -a)
                bottom_total += a

            # バランスをとる
            # topの方が多いなら調整
            while len(top) - len(bottom) > 0:
                heappush(bottom, -top[0])
                bottom_total += top[0]
                top_total -= heappop(top)
            # bottomの方が1よりも多いなら調整
            while len(bottom)-len(top) > 1:
                heappush(top, -bottom[0])
                top_total += -bottom[0]
                bottom_total -= -heappop(bottom)
        else:
            tot = btot
            tot += (len(bottom)*(-bottom[0]) - bottom_total)
            tot += (top_total - len(top)*(-bottom[0]))
            print(-bottom[0], tot)
        # print("長さ", len(bottom), len(top))
    # print(bottom, top)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
q=int(input())
a=0
b=0
g,l,ans=map(int,input().split())
r=l
now=1
from heapq import heappop, heappush
le,ri=[],[]
for i in range(q-1):
    cin=tuple(map(int,input().split()))
    if cin[0]==2:
        print(l,ans)
    else:
        x=cin[1]
        ans+=cin[2]
        if not(l<=x<=r):
            ans+=min(abs(x-l),abs(r-x))
        now+=1
        if now%2:
            heappush(le,-min(l,r,x))
            heappush(ri,max(l,r,x))
            l=l+r+x-max(l,r,x)-min(l,r,x)
            r=l
        else:
            if l<=x:
                heappush(ri,x)
                r=heappop(ri)
            else:
                heappush(le,-x)
                l,r=-heappop(le),l