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: Time Limit Exceeded

Solution code:

import queue

que_small=queue.PriorityQueue()
small_sum=0
que_s_size=0
que_b_size=0
que_big=queue.PriorityQueue()
big_sum=0

Q=int(input())
ans = []
b_sum=0
for i in range(Q):
    q=input().split()    
    if len(q)>1:
        a=int(q[1])
        if que_s_size==0:
            que_small.put(-a)
            small_sum+=a
            que_s_size+=1
        elif que_s_size>que_b_size:
            c=-que_small.get()
            small_sum-=c
            if c>a:
                que_big.put(c)
                big_sum+=c
                que_small.put(-a)
                small_sum+=a
            else:
                que_big.put(a)
                big_sum+=a
                que_small.put(-c)
                small_sum+=c
            que_b_size+=1
        else:
            c=-que_small.get()
            small_sum-=c
            d=que_big.get()
            big_sum-=d
            if a>d:
                que_big.put(a)
                big_sum+=a
                que_small.put(-c)
                que_small.put(-d)
                small_sum+=c+d
            else:
                que_big.put(d)
                big_sum+=d
                que_small.put(-a)
                que_small.put(-c)               
                small_sum+=a+c
            que_s_size+=1

        b_sum+=int(q[2])
    else:
        if que_s_size>que_b_size:
            c=-que_small.get()
            S = b_sum+big_sum-small_sum+c
            ans.append(str(c)+" "+str(S))
            que_small.put(-c)
        else:
            c=-que_small.get()
            S = b_sum+big_sum-small_sum
            ans.append(str(c)+" "+str(S))
            que_small.put(-c)
            

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import heapq
Q = int(input())
A = []
B = 0
l = 0
for _ in [0]*Q:
    s = input().split()
    if s[0]=="1":
        heapq.heappush(A,int(s[1]))
        B += int(s[2])
        l += 1
    else:
        q = [heapq.heappop(A) for _ in [0]*((l-1)//2)]
        m = A[0]
        A = q+A
        s = sum(abs(a-m) for a in A)
        print(m,B+s)

Submission status: Time Limit Exceeded

Solution code:
import heapq

q = int(input())

# 中央値との大小で集団を２つに分けて管理したいぞ
_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            # 最大ヒープ
            heapq.heappush(a_small, -a)
            total += abs(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            # 最小ヒープ
            heapq.heappush(a_large, a)
            total += abs(a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        # total = 0
        x = -a_small[0]
        # for small in a_small:
        #     total += abs(x+small)
        # for large in a_large:
        #     total += abs(x-large)
        print(x, total+cons)

Submission status: Time Limit Exceeded

Solution code:
import bisect

def cul(a,b,m):
    ans=0
    for i in a:
        ans+=abs(m-i)
    
    return ans+b

q=int(input())
b=0
a=[]
for i in range(q):
    p=input()
    if p=="2":
        if len(a)%2==1:
            m=a[len(a)//2]
        else:
            m=a[len(a)//2-1]
        print(m,cul(a,b,m))
        
    else:
        cq,ai,bi=map(int,p.split())
        b+=bi
        index = bisect.bisect_left(a, ai)
        a.insert(index, ai)

Submission status: Time Limit Exceeded

Solution code:
a,b=0,0
am=[]
amin=1000000000
amax=-1000000000
num=0

def fmin(am,b,amin,amax,num):
  kmin=1000000000000000000
  imin=amin
  for i in range(amin,amax+1):
    k=0
    for j in range(num):
      k+=abs(am[j]-i)
    if kmin>k:
      kmin=k
      imin=i
  print(imin,kmin+b)
  return

for _ in range(int(input())):
  q=input()
  if q=="2":
    fmin(am,b,amin,amax,num)
  else:
    t,a1,b1=map(int,q.split())
    am+=[a1]
    b+=b1
    amin=min(amin,a1)
    amax=max(amax,a1)
    num+=1

Submission status: Time Limit Exceeded

Solution code:

import bisect


def submit():
    query_n = int(input())

    alist = []
    bsum = 0
    count = 0

    for i in range(query_n):
        query = input()

        if query.startswith('1'):
            _, a, b = map(int, query.split())

            bisect.insort_left(alist, a)
            bsum += b
            count += 1
        else:
            # query = '2'
            if count % 2 == 1:
                idx = count // 2
            else:
                idx = count // 2 - 1

            x = alist[idx]
            result = 0
            for a in alist:
                result += abs(x - a)
            result += bsum

            print('{} {}'.format(x, result))



if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

Solution code:
import queue

que_small=queue.PriorityQueue()
small_sum=0
que_big=queue.PriorityQueue()
big_sum=0

Q=int(input())
ans = []
b_sum=0
for i in range(Q):
    q=input().split()    
    if len(q)>1:
        a=int(q[1])
        if que_small.qsize()==0:
            que_small.put(-a)
            small_sum+=a
        elif que_small.qsize()>que_big.qsize():
            c=-que_small.get()
            small_sum-=c
            if c>a:
                que_big.put(c)
                big_sum+=c
                que_small.put(-a)
                small_sum+=a
            else:
                que_big.put(a)
                big_sum+=a
                que_small.put(-c)
                small_sum+=c
        else:
            c=-que_small.get()
            small_sum-=c
            d=que_big.get()
            big_sum-=d
            if a>d:
                que_big.put(a)
                big_sum+=a
                que_small.put(-c)
                que_small.put(-d)
                small_sum+=c+d
            else:
                que_big.put(d)
                big_sum+=d
                que_small.put(-a)
                que_small.put(-c)               
                small_sum+=a+c

        b_sum+=int(q[2])
    else:
        if que_small.qsize()>que_big.qsize():
            c=-que_small.get()
            S = b_sum+big_sum-small_sum+c
            ans.append(str(c)+" "+str(S))
            que_small.put(-c)
        else:
            c=-que_small.get()
            S = b_sum+big_sum-small_sum
            ans.append(str(c)+" "+str(S))
            que_small.put(-c)
            

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li_a = []
b=0
for i in range(n):
    temp = input()
    if temp == "2":
        li_a.sort()
        if len(li_a)%2 == 0:
            ans_a = li_a[len(li_a)//2-1]
        else:
            ans_a = li_a[(len(li_a)-1)//2]
        ans_b = 0
        for a in li_a:
            ans_b += abs(a-ans_a)
        ans_b += b
        print(ans_a,ans_b)
    else:
        z,aa,bb=temp.split(" ")
        li_a.append(int(aa))
        b+=int(bb)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
A=[]
b=0
def f(A,b,n):
  res=0
  for a in A:
    res+=abs(a-n)
  return res+b
for _ in range(q):
  L=[int(i) for i in input().split()]
  if L[0]==1:
    A.append(L[1])
    b+=L[2]
  else:
    A.sort()
    n=A[(len(A)-1)//2]
    print(n,f(A,b,n))

Submission status: Time Limit Exceeded

Solution code:
import statistics

q = int(input())

a_list = []
b = 0
for i in range(q):
    qi = list(map(int,input().split()))
    if qi[0] == 1:
        # 更新クエリ
        a_list.append(qi[1])
        b = b + qi[2]
    else:
        # 求解クエリ
        med = statistics.median_low(a_list)
        a_sum = sum([ abs(j - med) for j in a_list])
        print("{0} {1}".format(med,b+a_sum))

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q = int(input())

A, B = [], 0
for _ in range(Q):
    q = list(map(int, input().split()))
    if len(q) == 3:
        bisect.insort(A, q[1])
        B += q[2]
    elif len(q) == 1:
        lA = len(A)
        if lA % 2 == 0:
            print(A[lA // 2 - 1], sum(A[lA // 2:]) - sum(A[:lA // 2]) + B)
        else:
            print(A[lA // 2], sum(A[lA // 2 + 1:]) - sum(A[:lA // 2]) + B)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def fn(b, a_s):
    a_s = np.sort(np.array(a_s))
    mini =  10 ** 20
    res = - 10 ** 20

    sum = b
    for a in a_s:
        sum += abs(a_s-a)
    res = a_s[np.argmin(sum)]
    mini = np.min(sum)

    return res, mini

q = int(input())
bsum = 0
a_s = []
for i in range(q):
    que = list(map(int, input().split()))
    if len(que) == 1:
        res, mini = fn(bsum, a_s)
        print(res, mini)
    else:
        a_s.append(que[1])
        bsum += que[2]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li_a = []
b=0
for i in range(n):
    li_a.sort()
    temp = input()
    if temp == "2":
        if len(li_a)%2 == 0:
            ans_a = li_a[len(li_a)//2-1]
        else:
            ans_a = li_a[(len(li_a)-1)//2]
        ans_b = 0
        for a in li_a:
            ans_b += abs(a-ans_a)
        ans_b += b
        print(ans_a,ans_b)
    else:
        z,aa,bb=temp.split(" ")
        li_a.append(int(aa))
        b+=int(bb)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def quicksort(x):
    if x==[]: return []
    s = quicksort([a for a in x[1:] if a <= x[0]])
    b = quicksort([a for a in x[1:] if a > x[0]])
    return(s+[x[0]]+b)
Q = int(input())
A = []
B = 0
l = 0
for _ in [0]*Q:
    s = input().split()
    if s[0]=="1":
        heapq.heappush(A,int(s[1]))
        B += int(s[2])
        l += 1
    else:
        A = quicksort(A)
        m = A[(l-1)//2]
        s = sum(abs(a-m) for a in A)
        print(m,B+s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import bisect
q=[]
a=[]
b=0
l=0
ans=0
for _ in range(n):
    p=[int(i) for i in input().split()]
    if p[0]==1:
        b+=p[2]
        insert_index = bisect.bisect_left(a,p[1])  
        a.insert(insert_index,p[1])
        l+=1
    if p[0]==2:
        if l%2==0:
            al=a[0:l//2]
            ar=a[l//2:l]
            print(a[l//2-1],sum(ar)-sum(al)+b)
        else:
            al=a[0:l//2]
            ar=a[l//2+1:l]
            c=a[l//2]
            print(c,sum(ar)-sum(al)+b)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
a=[]
b=0
for i in range(q):
        query=list(map(int,input().split()))
        if query[0]==1:
                a.append(query[1])
                b+=query[2]
        if query[0]==2:
                a.sort()
                l=len(a)
                if l%2==1:
                        a_=a[int((l-1)/2)]
                        m=sum(a[int((l-1)/2)+1:])-sum(a[:int((l-1)/2)])+b
                else:
                        a_=a[int(l/2-1)]
                        m=sum(a[int(l/2-1)+1:])-sum(a[:int(l/2-1)])-a_+b
                print(a_,m)

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
A=[]
b=0
def f(A,b,n):
  res=0
  for a in A:
    res+=abs(a-n)
  return res+b
for _ in range(q):
  L=[int(i) for i in input().split()]
  if L[0]==1:
    A.append(L[1])
    b+=L[2]
  else:
    A.sort()
    n=A[(len(A)-1)//2]
    print(n,f(A,b,n))

Submission status: Time Limit Exceeded

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())
    point = []
    lenq = 0
    constant = 0
    for i in range(Q):
        query = [int(i) for i in line_input()]
        if query[0] == 1:
            constant += query[2]
            point.insert(bisect_left(point, query[1]),query[1])
            lenq += 1
        else:
            j = point[(lenq - 1)//2]
            ans = 0
            for p in point:
                ans += abs(p - j)
            print(j, ans + constant)
    

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

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

q = int(input())

def f(x):
    return 0

aaa = []
len_aaa = 0
def update(f, a, b):
    bisect.insort_left(aaa, a)
    global len_aaa
    len_aaa += 1
    return lambda x: f(x) + abs(x-a) + b

def get_min_x():
    if len_aaa % 2 == 0:
        min_x = aaa[len_aaa//2 - 1]
    else:
        min_x = aaa[len_aaa//2]
    print(str(min_x) + " " + str(f(min_x)))

for i in range(q):
    s = input()

    if s.startswith("1"):
        a,b = map(int, s[2:].split(" "))
        f = update(f, a, b)
    else:
        get_min_x()

a = set()

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
q0=int(input())
ind=0
a=[]
b=[]
for iii in range(q0):
  q=[int(_) for _ in input().split()]
  lenq=len(q)
  if lenq==1:
    meda=median(a)
    ind=sum([abs(_a-meda) for _a in a])+sum(b)
    i=1
    while sum([abs(_a-i-meda) for _a in a])+sum(b)==ind:
      i+=1
    print(int(meda-i+1),int(ind))
  elif lenq==3:
    a.append(q[1])
    b.append(q[2])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li_a = []
b=0
for i in range(n):
    temp = input()
    if temp == "2":
        if len(li_a)%2 == 0:
            ans_a = li_a[len(li_a)//2-1]
        else:
            ans_a = li_a[(len(li_a)-1)//2]
        ans_b = 0
        for a in li_a:
            ans_b += abs(a-ans_a)
        ans_b += b
        print(ans_a,ans_b)
    else:
        z,aa,bb=temp.split(" ")
        li_a.append(int(aa))
        li_a.sort()
        b+=int(bb)

Submission status: Time Limit Exceeded

Solution code:
def fn(b, a_s):
    a_s.sort()
    mini =  10 ** 20
    res = - 10 ** 20
    for x in a_s:
        sum = b
        for a in a_s:
            sum += abs(x-a)
        if sum < mini:
            mini = sum
            res = x

    return res, mini

q = int(input())
bsum = 0
a_s = []
for i in range(q):
    que = list(map(int, input().split()))
    if len(que) == 1:
        res, mini = fn(bsum, a_s)
        print(res, mini)
    else:
        a = que[1]
        a_s.append(a)
        b = que[2]
        bsum += b

Submission status: Time Limit Exceeded

Solution code:
# Binary Indexed Tree (Fenwick Tree)
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)}
    #for i in range(len(list1)):
    #    list1[i] = memo[list1[i]]
    return memo, len(list2)

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


#値を管理するBIT
bit = BIT(len_memo)
#要素数を管理するBITに
bit1 = BIT(len_memo)

x = []
b = 0
for i in range(q):
    if info[i][0] == 1:
        bit.add(memo[info[i][1]], info[i][1])
        bit1.add(memo[info[i][1]], 1)
        b += info[i][2]
        x.append(info[i][1])
        x = sorted(x)
    if info[i][0] == 2:
        median_x = x[(len(x)-1)//2]
        sum1 = bit.get(0, memo[median_x])
        num1 = bit1.get(0, memo[median_x])
        sum2 = bit.get(memo[median_x], len_memo)
        num2 = bit1.get(memo[median_x], len_memo)
        #print(median_x, sum1,num1, sum2, num2)
        print(median_x, abs(num1*median_x - sum1) + abs(num2*median_x - sum2) + b)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
Q=int(input())
alist=np.array([], dtype='int64')
b=0
cnt=0
for _ in range(Q):
    s=input()
    if s[0]=='1':
        cnt+=1
        _,ra,rb=map(int, s.split())
        alist=np.append(alist, ra)
        b+=rb
    if s[0]=='2':
        alist=np.sort(alist)
        index = int((cnt+1)/2)-1
        if cnt % 2 == 0:
            print(alist[index], -np.sum(alist[:index])+np.sum(alist[index+1:])-alist[index]+b)
        if cnt % 2 == 1:
            print(alist[index], -np.sum(alist[:index])+np.sum(alist[index+1:])+b)

Submission status: Time Limit Exceeded

Solution code:
def main():
	q = int(input())
	lst = []
	b = 0
	qq = 0
	for i in range(q):
		qy = list(map(int, input().split()))
		if qy[0] == 1:
			lst += [qy[1]]
			b += qy[2]
			qq += 1
		else:
			lst.sort()
			mark = (qq-1) // 2
			lmark = lst[mark]
			ans = 0
			for j in lst:
				ans += abs(lmark - j)
			print(lst[mark], ans + b)
		
main()

Submission status: Time Limit Exceeded

Solution code:
import statistics
q = int(input())
a = []
b = 0
for i in range(q):
  x = list(map(int, input().split()))
  if x[0] == 1:
    a.append(x[1])
    b += x[2]
  else:
    med = statistics.median_low(a)
    print(med, sum([abs(y - med) for y in a]) + b)

Submission status: Time Limit Exceeded

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

q = int(input())
a = []
b = 0
n = 0

for i in range(q):
    query = input()
    if query[0] == "1":
        _, _a, _b = map(int, query.split())
        bisect.insort(a, _a)
        b += _b
        n += 1
    else:
        min_x = a[(n - 1) // 2]
        min_y = b
        for i in range(n // 2):
            min_y += a[-(i + 1)] - a[i]
        print(min_x, min_y)

Submission status: Time Limit Exceeded

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

q = int(input())
a = []
b = 0
n = 0

for i in range(q):
    query = input()
    if query[0] == "1":
        _, _a, _b = map(int, query.split())
        a.append(_a)
        b += _b
        n += 1
    else:
        a.sort()
        min_x = a[(n - 1) // 2]
        min_y = b
        for i in range(n // 2):
            min_y += a[-(i + 1)] - a[i]
        print(min_x, min_y)

Submission status: Time Limit Exceeded

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

q = int(input())
a = []
b = 0
n = 0

for i in range(q):
    query = input()
    if query[0] == "1":
        _, _a, _b = map(int, query.split())
        a.append(_a)
        b += _b
        n += 1
    else:
        a.sort()
        min_x = a[(n - 1) // 2]
        min_y = b
        for i in range(n):
            min_y += abs(min_x - a[i])
        print(min_x, min_y)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
Q = int(input().rstrip())
queries = []
for _ in range(Q):
    queries.append(list(map(int, input().rstrip().split(" "))))

bias = 0
vs = []

for query in queries:
    if len(query) == 3:
        _, p, b = query
        bisect.insort_left(vs, p)
        bias += b
    else:
        i = (len(vs)+1) // 2 - 1
        p = vs[i]
        l = p*i - sum(vs[:i])
        r = sum(vs[i:]) - (p*(len(vs)-i))
        s = l + r
        #s = sum(abs(p-v) for v in vs)
        print(p, s+bias)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
a = []
b = 0
n = 0

for i in range(q):
    query = input()
    if query[0] == "1":
        _, _a, _b = map(int, query.split())
        a.append(_a)
        b += _b
        n += 1
    else:
        a.sort()
        min_x = a[(n - 1) // 2]
        min_y = b
        for i in range(n):
            min_y += abs(min_x - a[i])
        print(min_x, min_y)

Submission status: Time Limit Exceeded

Solution code:
import sys
Q = int(input().rstrip())
queries = []
for _ in range(Q):
    queries.append(list(map(int, input().rstrip().split(" "))))

bias = 0
vs = []

for query in queries:
    if len(query) == 3:
        _, p, b = query
        vs.append(p)
        bias += b
    else:
        vs = sorted(vs)
        p = vs[(len(vs)+1) // 2 - 1]
        s = sum(abs(p-v) for v in vs)
        print(p, s+bias)

Submission status: Accepted

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


ans = 0
left,right = [],[]
heapify(left)
heapify(right)
r = 0

Q = I()
for _ in range(Q):
    q = LI()
    if q[0] == 1:
        a,b = q[1:]
        ans += b
        if r == 0:
            heappush(left,-a)
        elif r == 1:
            x1 = -heappop(left)
            ans += abs(a-x1)
            if x1 < a:
                x1,a = a,x1
            heappush(left,-a)
            heappush(right,x1)
        else:
            x1 = -heappop(left)
            x2 = heappop(right)
            if r % 2 == 0:
                ans += max(0,x1-a,a-x2,0)
                heappush(left,-x1)
                if a <= x2:
                    heappush(left,-a)
                    heappush(right,x2)
                else:
                    heappush(left,-x2)
                    heappush(right,a)
            else:
                ans += abs(x1-a)
                heappush(right,x2)
                if a <= x1:
                    heappush(left,-a)
                    heappush(right,x1)
                else:
                    heappush(left,-x1)
                    heappush(right,a)
        r += 1
    else:
        x = -heappop(left)
        print(x,ans)
        heappush(left,-x)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify,heappop,heappush
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


ans = 0
left,right = [],[]
heapify(left)
heapify(right)
r = 0

Q = I()
for _ in range(Q):
    q = LI()
    if q[0] == 1:
        a,b = q[1:]
        ans += b
        if r == 0:
            heappush(left,-a)
        elif r == 1:
            x1 = -heappop(left)
            ans += abs(a-x1)
            if x1 < a:
                x1,a = a,x1
            heappush(left,-a)
            heappush(right,x1)
        else:
            x1 = -heappop(left)
            x2 = heappop(right)
            if r % 2 == 0:
                ans += max(0,x1-a,a-x2,0)
                if a <= x2:
                    heappush(left,-x1)
                    heappush(left,-a)
                    heappush(right,x2)
                else:
                    heappush(left,-x1)
                    heappush(left,-x2)
                    heappush(right,a)
            else:
                ans += abs(x1-a)
                if a <= x1:
                    heappush(left,-a)
                    heappush(right,x1)
                    heappush(right,x2)
                else:
                    heappush(left,-x1)
                    heappush(right,a)
                    heappush(right,x2)
        r += 1
    else:
        x = -heappop(left)
        print(x,ans)
        heappush(left,-x)

Submission status: Accepted

Solution code:
import heapq
Q = int(input())
ans = 0
L = []
R = []
for _ in range(Q):
    q = input()
    if q[0] == '1':
        _, a, b = map(int, q.split())
        ans += b
        if len(L) > 0 and not -L[0] <= a <= R[0]:
            ans += min(abs(a + L[0]), abs(a - R[0]))
        l = heapq.heappushpop(L, -a)
        r = heapq.heappushpop(R, a)
        heapq.heappush(L, -r)
        heapq.heappush(R, -l)
    else:
        print(-L[0], ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    Q = int(readline())

    hi = []
    lo = []
    hi_sum = lo_sum = 0
    b_sum = 0

    ans = []
    for _ in range(Q):
        A = list(map(int, readline().split()))
        if len(A) == 3:
            a, b = A[1], A[2]
            b_sum += b

            if not lo:
                lo.append(-a)
                lo_sum += a
            else:
                vec = [a]
                vec.append(-heappop(lo))
                lo_sum -= vec[1]
                if hi:
                    vec.append(heappop(hi))
                    hi_sum -= vec[2]
                    
                vec.sort()
                
                if len(vec) == 2:
                    heappush(lo, -vec[0])
                    heappush(hi, vec[1])
                    lo_sum += vec[0]
                    hi_sum += vec[1]
                elif len(lo) > len(hi):
                    heappush(lo, -vec[0])
                    heappush(hi, vec[1])
                    heappush(hi, vec[2])
                    lo_sum += vec[0]
                    hi_sum += vec[1]
                    hi_sum += vec[2]
                else:
                    heappush(lo, -vec[0])
                    heappush(lo, -vec[1])
                    heappush(hi, vec[2])
                    lo_sum += vec[0]
                    lo_sum += vec[1]
                    hi_sum += vec[2]
        else:
            x = -lo[0]
            val = x * (len(lo) - len(hi)) - lo_sum + hi_sum + b_sum
            ans.append((x, val))

    for x, val in ans:
        print(x, val)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    Q = int(readline())

    hi = []
    lo = []
    hi_sum = lo_sum = 0
    b_sum = 0

    ans = []
    for _ in range(Q):
        A = list(map(int, readline().split()))
        if len(A) == 3:
            a, b = A[1], A[2]
            b_sum += b

            if not lo:
                lo.append(-a)
                lo_sum += a
            else:
                if a <= -lo[0]:
                    heappush(lo, -a)
                    lo_sum += a
                else:
                    heappush(hi, a)
                    hi_sum += a

            if len(hi) > len(lo):
                x = heappop(hi)
                hi_sum -= x
                heappush(lo, -x)
                lo_sum += x
            elif len(hi) + 1 < len(lo):
                x = -heappop(lo)
                lo_sum -= x
                heappush(hi, x)
                hi_sum += x
        else:
            x = -lo[0]
            val = x * (len(lo) - len(hi)) - lo_sum + hi_sum + b_sum
            ans.append((x, val))

    for x, val in ans:
        print(x, val)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    Q = int(readline())

    hi = []
    lo = []
    hi_sum = lo_sum = 0
    b_sum = 0

    ans = []
    for _ in range(Q):
        A = list(map(int, readline().split()))
        if len(A) == 3:
            a, b = A[1], A[2]
            b_sum += b

            if not lo:
                lo.append(-a)
                lo_sum += a
            else:
                if a <= -lo[0]:
                    heappush(lo, -a)
                    lo_sum += a
                else:
                    heappush(hi, a)
                    hi_sum += a

            if len(hi) > len(lo):
                x = heappop(hi)
                hi_sum -= x
                heappush(lo, -x)
                lo_sum += x
            elif len(hi) + 1 < len(lo):
                x = -heappop(lo)
                lo_sum -= x
                heappush(hi, x)
                hi_sum += x
        else:
            x = -lo[0]
            val = x * (len(lo) - 1) - (lo_sum - x) + hi_sum - x * len(hi) + b_sum
            ans.append((x, val))

    for x, val in ans:
        print(x, val)

    return


if __name__ == '__main__':
    main()