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())
ans = []
mini = 0
left, right = [], []
cnt = 0
mid = None
for _ in range(q):
    qi = input()
    if qi == '2':
        if cnt%2 == 0:
            ans.append([-left[0], mini])
        else:
            ans.append([mid, mini])
    else:
        kind, a, b = map(int, qi.split())
        if cnt%2 == 1:
            mini += abs(mid-a) + b
            heapq.heappush(left, -min(mid, a))
            heapq.heappush(right, max(mid, a))
            mid = None
        else:
            if cnt == 0:
                mid = a
                mini = b
                cnt += 1
                continue
            l = -heapq.heappop(left)
            r = heapq.heappop(right)
            if a <= l:
                mini += l-a + b
                heapq.heappush(left, -a)
                heapq.heappush(right, r)
                mid = l
            elif a <= r:
                mini += b
                heapq.heappush(left, -l)
                heapq.heappush(right, r)
                mid = a
            else:
                mini += a-r + b
                heapq.heappush(left, -l)
                heapq.heappush(right, a)
                mid = r
        cnt += 1

for i, j in ans:
    print(i, j)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # 0は絶対に入れない!!
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            i += 1
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考　よくわかってない
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i

        def debug(self, k):
            return [self.sum(i) for i in range(k)]
    def compress(list1):
        list2 = sorted(set(list1))
        memo = {value: index for index, value in enumerate(list2)}
        for i in range(len(list1)):
            list1[i] = memo[list1[i]]
        return memo, len(list2)
    n = I()
    Q = [LI()for _ in range(n)]
    A = []
    for q in Q:
        if q[0]==2:
            continue
        a, b = q[1:]
        A.append(a)
    memo,N = compress(A)
    #print(memo)
    #print(N)
    bit = Bit(N+1)
    bit_a = Bit(N+1)
    location = defaultdict(int)
    num = 0
    B = 0
    ans = []
    for q in Q:
        if q[0]==2:
            x = bit.search((num+1)//2)
            #print(x,bit_a.sum(x),location[x])
            l = location[x]
            rep = l*bit.sum(x)-bit_a.sum(x)+B
            rep += bit_a.sum(N) - bit_a.sum(x) - l*(bit.sum(N) - bit.sum(x))
            ans.append((location[x],rep))
            continue
        a, b = q[1:]
        B += b
        bit.add(memo[a])
        bit_a.add(memo[a],a)
        location[memo[a]] = a
        num += 1

    for v in ans:
        print(" ".join(map(str,v)))
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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;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:
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;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:
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;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:
import sys
input=sys.stdin.buffer.readline
q=int(input())
from heapq import heapify, heappop, heappush
L=[]
R=[]
s=0
ans=0
c=0
l,r=-10**10,10**10
for i in range(q):
    j=tuple(map(int ,input().split()))
    if j[0]==1:
        x,y=j[1],j[2]
        s+=1
        ans+=y
        if not(l<=x<=r):ans+=min(abs(l-x),abs(r-x))
        if s==1:
            heappush(L,-x)
            l,r=x,x
        elif s%2:
            if -L[0]>=x:
                heappush(L,-x)
                l,r=-L[0],-L[0]
            else:
                heappush(R,x)
                l=heappop(R)
                r=l
                heappush(L,-l)
        else:
            if -L[0]<=x:
                heappush(R,x)
            else:
                heappush(L,-x)
                heappush(R,-heappop(L))    
            l,r=-L[0],R[0]
    else:
        print(l,ans)
        #continue

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def main():
    Q = int(input())
    total_b = 0
    total_a = 0
    less_than_middle = 0
    left = []
    right = []
    cnt = 0
    for _ in range(Q):
        query = tuple(map(int,input().split()))
        if query[0] == 1:
            a,b = query[1:]
            total_b += b
            total_a += a
            cnt += 1
            heappush(right,a)
            while left and right and (-left[0] > right[0]):
                p = -heappop(left)
                q = heappop(right)
                heappush(left,-q)
                heappush(right,p)
                less_than_middle += -p + q
            if cnt%2 == 0:
                p = heappop(right)
                heappush(left,-p)
                less_than_middle += p
        else:
            if cnt%2 == 0:
                x = -left[0]
                ans = total_a - 2*less_than_middle + total_b
                print(x,ans)
            else:
                x = right[0]
                ans = total_a - 2*less_than_middle - x + total_b
                print(x,ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop

q = int(input())
left = []
right = []
bias = 0
sum_left = 0
sum_right = 0

for _ in range(q):
    query = input().split()
    if len(query) == 3:
        n, a, b = [int(x) for x in query]
        bias += b
        if not right:
            if not left:
                heappush(left, -a)
                sum_left += a
            else:
                l = -heappop(left)
                if l > a:
                    heappush(left, -a)
                    heappush(right, l)
                    sum_right += l
                    sum_left += (a - l)
                else:
                    heappush(left, -l)
                    heappush(right, a)
                    sum_right += a
            continue
        l, r = -heappop(left), heappop(right)
        if len(left) == len(right):
            if a > r:
                heappush(right, a)
                heappush(left, -l)
                heappush(left, -r)
                sum_left += r
                sum_right += (a - r)
            else:
                heappush(left, -l)
                heappush(left, -a)
                heappush(right, r)
                sum_left += a
        else:
            if a < l:
                heappush(right, r)
                heappush(right, l)
                heappush(left, -a)
                sum_left += (a - l)
                sum_right += l
            else:
                heappush(right, r)
                heappush(right, a)
                heappush(left, -l)
                sum_right += a
    else:
        median = -heappop(left)
        print(median, -sum_left + sum_right + (-len(right) + len(left) + 1)*(median) + bias)
        heappush(left, -median)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1
  
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return memo, len(list2)

q = int(readline())
L = [list(map(int,readline().split())) for i in range(q)]
 
#座圧する
chk = []
for i in range(q):
    if L[i][0] == 1:
        chk.append(L[i][1])
        
memo, len_memo = compress(chk)
memo_inv = dict([(v,k) for k,v in memo.items()])

#値を管理するBIT
bit = Bit(len_memo)
#要素数を管理するBIT
num = Bit(len_memo)
  
s = 0
cnt = 0
for i in range(q):
  que = L[i]
  if que[0] == 1:
    a,b,c = que
    s += c
    cnt += 1
    bit.add(memo[b]+1,b)
    num.add(memo[b]+1,1)
  else:
    d = num.lower_bound((cnt+1)//2)
    m = memo_inv[d-1]
    sum1 = bit.sum(d)
    num1 = num.sum(d)
    sum2 = bit.sum(len_memo)-bit.sum(d)
    num2 = num.sum(len_memo)-num.sum(d)
    print(m,abs(num1*m-sum1)+abs(num2*m-sum2)+s)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class BinaryIndexedTree:
    # 1-indexed
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    
    def add(self, i, x):
        # Accessed by 0-indexed
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def sum(self, i):
        # [0, i)
        res = 0
        while i:
            res += self.data[i]
            i -= i & -i
        return res
    
    def bisect_left(self, w):
        if w <= 0:
            return 0
        i = 0
        k = 1 << (self.n.bit_length() - 1)
        while 0 < k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k >>= 1
        return i + 1


def solve():
    Q = int(rl())
    queries = [tuple(map(int, rl().split())) for _ in range(Q)]
    
    a = []
    for query in queries:
        if query[0] == 1:
            a.append(query[1])
    sorted_a = sorted(set(a))
    a_to_idx = {val: idx for idx, val in enumerate(sorted_a)}
    idx_to_a = {val: key for key, val in a_to_idx.items()}
    
    N = len(sorted_a)
    bit0 = BinaryIndexedTree(N)
    bit1 = BinaryIndexedTree(N)
    
    b_sm = 0
    cnt = 0
    for query in queries:
        if query[0] == 1:
            _, a, b = query
            bit0.add(a_to_idx[a], a)
            bit1.add(a_to_idx[a], 1)
            b_sm += b
            cnt += 1
        else:
            med_x = idx_to_a[bit1.bisect_left((cnt + 1) // 2) - 1]
            under_sm = bit0.sum(a_to_idx[med_x])
            under_n = bit1.sum(a_to_idx[med_x])
            over_sm = bit0.sum(N) - under_sm
            over_n = bit1.sum(N) - under_n
            print(med_x, abs(under_n * med_x - under_sm) + abs(over_n * med_x - over_sm) + b_sm)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    q = int(input())
    b = 0
    hq_l, hq_r = [], []
    sum_l, sum_r = 0, 0

    for _ in range(q):
        a = list(map(int, input().split()))
        if a[0] == 1:
            b += a[2]
            if len(hq_l)==0 or a[1] <= -hq_l[0]:
                heappush(hq_l, -a[1])
                sum_l += a[1]
            else:
                heappush(hq_r, a[1])
                sum_r += a[1]
        else:
            while len(hq_l)-1 > len(hq_r):
                sum_l -= -hq_l[0]
                sum_r += -hq_l[0]
                m = -heappop(hq_l)
                heappush(hq_r, m)
            while len(hq_l) < len(hq_r):
                sum_l += hq_r[0]
                sum_r -= hq_r[0]
                m = -heappop(hq_r)
                heappush(hq_l, m)
            print(-hq_l[0],  (-hq_l[0]*len(hq_l)) - sum_l + sum_r - (-hq_l[0]*len(hq_r)) + b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
q = int(input())
l = []
r = []
ai = 0
bs = 0
for i in range(q):
    ipt = list(map(int,input().split()))
    if ipt[0] == 1:
        al = heapq.heappushpop(l,-ipt[1])
        ar = heapq.heappushpop(r,ipt[1])
        ai -= (al+ar)
        heapq.heappush(l,-ar)
        heapq.heappush(r,-al)
        bs += ipt[2]
    else:
        an = heapq.heappop(l)
        print(-an,bs+ai)
        heapq.heappush(l,an)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
def main():
    Q=int(input())

    ab_list=[]
    query_type=[]

    for i in range(Q):
        query=list(map(int,input().split()))
        query_type.append(query[0])
        if query[0]==1:
            ab_list.append((query[1],query[2]))

    #query_type->[1,1,2,1,2]
    #ab_list->[(a,b),(a,b),(a,b)]

    L=[]
    R=[]

    ini=0

    counter=0
    ab_pointer=0
    minF=0
    for i in query_type:
        if i==1:
            a_new=ab_list[ab_pointer][0]
            b_new=ab_list[ab_pointer][1]
            heappush(L,-1*a_new)
            heappush(R,a_new)
            Lmax=-1*heappop(L)
            Rmin=heappop(R)
            if Lmax<=Rmin:
                heappush(L,-1*Lmax)
                heappush(R,Rmin)
            else:
                heappush(L,-1*Rmin)
                heappush(R,Lmax)
            delta=abs(Lmax-Rmin)
            minF+=delta+b_new
            ab_pointer+=1
        else:
            minX=-1*heappop(L)
            print(str(minX)+" "+str(minF))
            heappush(L,-1*minX)



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from bisect import insort

class BIT():
 
    def __init__(self, n):
        '''
        n = 要素数
        添字は i = 0 ~ n-1 となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)
 
    def add(self, i, x):
        '''i番目の要素にxを加算する'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
 
    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
 
    def get(self, i, j):
        '''[i, j)の和を求める'''
        return self._sum(j) - self._sum(i)
  
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return memo, len(list2)

q = int(readline())
info = [list(map(int, input().split())) for i in range(q)]
 
#座圧する
li1 = []
for i in range(q):
    if info[i][0] == 1:
        li1.append(info[i][1])
        
memo, len_memo = compress(li1)

def median():
    ok = len_memo
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if 2 * bit1.get(mid, len_memo) <= cnt :
            ok = mid
        else:
            ng = mid
    return memo_inv[ng]
  
#値を管理するBIT
bit = BIT(len_memo)
#要素数を管理するBITに
bit1 = BIT(len_memo)
memo_inv = dict([(v,k) for k,v in memo.items()])
  
s = 0
cnt = 0
for i in range(q):
  que = info[i]
  if que[0] == 1:
    a,b,c = que
    s += c
    cnt += 1
    bit.add(memo[b],b)
    bit1.add(memo[b], 1)
  else:
    d = median()
    sum1 = bit.get(0, memo[d])
    num1 = bit1.get(0, memo[d])
    sum2 = bit.get(memo[d], len_memo)
    num2 = bit1.get(memo[d], len_memo)
    print(d, abs(num1*d- sum1) + abs(num2*d - sum2) + s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(Q):
    sb = 0

    l = []
    r = []
    sl = 0
    sr = 0

    for q in Q:
        if q[0] == 1:
            _, a, b = q
            heapq.heappush(l, -a)
            sl += a

            if len(l) > len(r) + 1:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a

            while l and r and -l[0] > r[0]:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a

                a = heapq.heappop(r)
                heapq.heappush(l, -a)
                sl += a
                sr -= a

            sb += b
        else:
            x = -l[0]
            print(x, abs(sl - len(l)*x) + abs(sr - len(r)*x) + sb)

def main():
    N = read_int()
    Q = [read_int_n() for _ in range(N)]
    slv(Q)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

alist=[]
hq_left,hq_right=[],[]
dummy,a1,b1=map(int,input().split())
heapq.heappush(hq_left,-a1)
heapq.heappush(hq_right,a1)
b=b1

min_arg=-hq_left[0]
min_diff=0
#min_value=b      
for _ in range(Q-1):
  query=list(map(int,input().split()))
  if len(query)==3:    
    dummy,ai,bi=query
    b+=bi
    
    max_left=-hq_left[0]
    min_right=hq_right[0]
    if ai<max_left:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_left,-ai)
      heapq.heappop(hq_left)
      heapq.heappush(hq_right,max_left)      
      min_diff+=max_left-ai
    elif min_right<ai:
      heapq.heappush(hq_right,ai)
      heapq.heappush(hq_right,ai)
      heapq.heappop(hq_right)
      heapq.heappush(hq_left,-min_right)      
      min_diff+=ai-min_right
    else:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_right,ai)      
  else:    
    min_arg=-hq_left[0]
    min_value=min_diff+b
    print(min_arg,min_value)

Submission status: Accepted

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

import heapq

Q = int(input())

ans = 0

INF = 10 ** 18

L_pque = []
R_pque = []

heapq.heappush(L_pque, +INF)
heapq.heappush(R_pque, +INF)

for _ in range(Q):
    tmp = tuple(map(str, input().split()))
    if len(tmp) == 1:
        print (-L_pque[0], ans)
    else:
        a = int(tmp[1])
        b = int(tmp[2])

        ans += b

        tmpA = -L_pque[0]
        tmpB = +R_pque[0]
        # print ('区間', tmpA, tmpB)

        if a < tmpA:
            ans += abs(tmpA - a)
        elif tmpB < a:
            ans += abs(a - tmpB)
        
        heapq.heappush(L_pque, -a)
        heapq.heappush(R_pque, +a)

        tmpA = -heapq.heappop(L_pque)
        tmpB = +heapq.heappop(R_pque)

        if tmpA <= tmpB:
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)
        else:
            tmpA, tmpB = tmpB, tmpA
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)

Submission status: Accepted

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

def main():
    Left = [10**10] # queri_num == 1の時はこっちが１多いことにする
    Right = [10**10]
    queri_num = 0 # mod 2
    const = 0
    min_val = 0

    """
    [a1, a2, ..., ai]の中央値を高速に求めないといけない所で分からず諦めた。。。

    発想は単純で、左側パートと右側パートを分けて管理しておいて、新しいクエリが来るごとに
    aを左に入れるか右に入れるか決めれば良い。
    ただし左右のパートをリストで管理するとaの挿入にO(N)かかってしまうので、ここでは
    ヒープによって管理する。なので挿入はO(logN)で可能。

    あと中央値における関数の最小値も求めないといけないが、これは基本的には単に|a - median|
    増えるだけなので、これもaの挿入時に逐次O(1)で決定可能。
    """

    Q = int(input())
    for _ in range(Q):
        queri = list(map(int, input().split()))
        if queri[0] == 2:
            x = -heappop(Left)
            print("{} {}".format(x, min_val + const))
            heappush(Left, -x)
        elif queri_num == 1:
            queri_num = 0
            const += queri[2]
            a = queri[1]
            mid = -heappop(Left)
            if a < mid:
                min_val += mid - a
                heappush(Left, -a)
                heappush(Right, mid)
            else:
                min_val += a - mid
                heappush(Left, -mid)
                heappush(Right, a)
        elif queri_num == 0:
            queri_num = 1
            const += queri[2]
            a = queri[1]
            left = -heappop(Left)
            right = heappop(Right)
            if a < left:
                min_val += left - a
                heappush(Left, -a)
                heappush(Left, -left)
                heappush(Right, right)
            elif a < right:
                # min_val is constant
                heappush(Left, -left)
                heappush(Left, -a)
                heappush(Right, right)
            else:
                min_val += a - right
                heappush(Left, -left)
                heappush(Left, -right)
                heappush(Right, a)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
q=int(input())
queries=[list(map(int,input().split()))for _ in range(q)]
l=[]
r=[]
ans=0
quecount=0
for query in queries:
  if query[0]==1:
    quecount+=1
    _,a,b=query
    ans+=b
    if quecount==1:
      mid=a
    elif quecount%2==1:
      if a<-l[0]:
        mid=-heappop(l)
        heappush(l,-a)
      elif r[0]<a:
        mid=heappop(r)
        heappush(r,a)
      else:
        mid=a
      ans+=abs(a-mid)
    else:
      ans+=abs(a-mid)
      heappush(l,-min(a,mid))
      heappush(r,max(a,mid))
  if query[0]==2:
    if quecount%2==1:
      ansind=mid
    else:
      ansind=-l[0]
    print(ansind,ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    q=int(input())
    Q=[tuple(map(int, input().split())) for _ in range(q)]
    asum=bsum=0
    from heapq import heappop, heappush
    s,l=[],[]
    mn=0
    for query in Q:
        if query[0]==1:
            a,b=query[1],query[2]
            bsum+=b
            E=[a,a]
            smx,lmn=a,a
            if s:
                smx=-heappop(s)
                E.append(smx)
            if l:
                lmn=heappop(l)
                E.append(lmn)
            if a<smx: mn+=smx-a
            elif lmn<a: mn+=a-lmn
            E.sort()
            for i in range(len(E)//2):
                heappush(s,-E[i])
                heappush(l,E[-1-i])
        else:
            print(-s[0], mn + bsum)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    Q = int(input())
    ans = 0
    l = []
    r = []
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            ans += query[2]
            heapq.heappush(l, -query[1])
            heapq.heappush(r, query[1])
            if -l[0] > r[0]:
                l_max = -1 * heapq.heappop(l)
                r_min = heapq.heappop(r)
                ans += abs(l_max-r_min)
                heapq.heappush(l, -r_min)
                heapq.heappush(r, l_max)

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






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    #n:要素数
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    #i番目(0-indexed)の値にxを足す
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    #sum[0, i)
    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

Q = int(input())
que = []
vals = []

for _ in range(Q):
    l = list(map(int, input().split()))
    que.append(l)
    
    if len(l)==3:
        vals.append(l[1])

idx = compress(vals)
rev_idx = defaultdict(int)

for k, v in idx.items():
    rev_idx[v] = k
    
N = len(list(idx.keys()))
bit1 = BIT(N)
bit2 = BIT(N)
b_acc = 0
cnt = 0

for i in range(Q):
    if len(que[i])==3:
        a, b = que[i][1], que[i][2]
        b_acc += b
        bit1.add(idx[a], 1)
        bit2.add(idx[a], a)
        cnt += 1
    else:
        l, r = 0, N-1
        
        while l<=r:
            m = (l+r)//2
            
            if bit1.acc(m+1)>=(cnt+1)//2:
                r = m-1
            else:
                l = m+1
        
        x = l
        lsum = bit1.acc(x)*rev_idx[x]-bit2.acc(x)
        rsum = bit2.acc(N)-bit2.acc(x)-(bit1.acc(N)-bit1.acc(x))*rev_idx[x]
        print(rev_idx[x], lsum+rsum+b_acc)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
q=int(input())
queries=[list(map(int,input().split()))for _ in range(q)]
l=[]
r=[]
ans=0
queonecount=0
mid=-1
for query in queries:
  if query[0]==1:
    queonecount+=1
    _,a,b=query
    ans+=b
    heappush(l,-a)
    heappush(r,a)
    midl=-heappop(l)
    midr=heappop(r)
    ans+=abs(midl-midr)
    heappush(l,-midr)
    heappush(r,midl)
  if query[0]==2:
    minind=-heappop(l)
    print(minind,ans)
    heappush(l,-minind)