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 bisect
import sys
input = sys.stdin.readline
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:
    n=bisect.bisect_left(A,L[1])
    A.insert(n,L[1])
    b+=L[2]
  else:
    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 = (lenq - 1)//2
            ans = sum(point[j:]) - sum(point[:j]) + point[j] * (2 * j - lenq) 
            print(point[j], ans + constant)
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
a = []
b = 0
c = 0

for i in range(q):
    if query[i][0] == 1:
        a.append(query[i][1])
        b += query[i][2]
    else:
        a.sort()
        a1 = (len(a)-1) // 2
        a2 = a[a1]
        c = 0
        for j in range(len(a)):
            c += abs(a[j]-a2)
        print(a2,c+b)

Submission status: Time Limit Exceeded

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

q = int(input())
al = []

s = 0
for i in range(q):
    query = input()
    if len(query) > 2:
        que, a, b = map(int, query.split())
        al.append(a)
        al.sort()
        s += b
    else:
        if len(al) % 2 == 1:
            x = al[(len(al) - 1) // 2]
        else:
            x = al[len(al) // 2 - 1]
        ans = sum([abs(x - i) for i in al])
        ans += s
        print(x, ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q = int(input())

A = []
A_size = 0
A_med_min = 0
A_med_max = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        #常にソート済リストを作れる
        bisect.insort_left(A,a)
        A_size+=1
        #中央値との差分からA群からなる最小値を更新
        sabun = 0
        if a<A_med_min:
            sabun = A_med_min - a
        elif a>A_med_max:
            sabun = a - A_med_max
        MIN_SCORE += sabun + b if A_size>1 else b
        #中央値の更新
        if A_size%2==0:
            A_med_min = A[(A_size//2)-1]
            A_med_max = A[A_size//2]
        else:
            A_med_min = A[A_size//2]
            A_med_max = A[A_size//2]
    elif q[0]=="2":
        print(A_med_min,MIN_SCORE)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

order = list(map(int, input().split()))
A = [order[1]]
len_A = 1
B = order[2]

for i in range(Q-1):
        order = list(map(int, input().split()))
        if order[0] == 1:
                B += order[2]
                idx = 0
                while idx < len_A and A[idx] < order[1]:
                        idx += 1
                A = A[:idx] + [order[1]] + A[idx:]
                len_A += 1
        else:
                if len_A % 2 == 1:
                        min_x = A[(len_A - 1) // 2]
                        min_f = B
                        for i in range(len_A):
                                min_f += abs(min_x - A[i])
                        print('{} {}'.format(min_x, min_f))
                else:
                        min_x = A[-1 + len_A // 2]
                        min_f = B
                        for i in range(len_A):
                                min_f += abs(min_x - A[i])
                        print('{} {}'.format(min_x, min_f))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import bisect
q=int(input())
h=[]
l=0 #hの要素数
b=0 #bの和
s=0 #絶対偏差の和
med=0
for _ in range(q):
    Tmp=tuple(map(int,input().split()))
    if Tmp[0]==1:
        b+=Tmp[2]
        if l%2:
            s+=abs(Tmp[1]-med)
        else:
            if l:
                med_next=h[(l-1)//2+1]
                if Tmp[1]<=med:
                    s+=abs(Tmp[1]-med)
                elif Tmp[1]>=med_next:
                    s+=abs(Tmp[1]-med_next)
            else:
                med=Tmp[1]
        l+=1
        bisect.insort(h,Tmp[1])
        med=h[(l-1)//2]
    else:
        print(med,s+b)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, asum, bsum, c = [], 0, 0, 0
for query in queries:
    if query[0] == '2':
        absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        # asum += a
        bsum += b
        c += 1

Submission status: Time Limit Exceeded

Solution code:
import bisect


Q = int(input())
Alist = []
S = 0
Bsum = 0
Qs = [input() for _ in range(Q)]
for query in Qs:
    if query[0] == "1":
        _, a, b = map(int, query.split(" "))
        Bsum += b
        Alist.insert(bisect.bisect_left(Alist, a), a)
        S += a
    else:
        key = len(Alist)
        S2 = S
        minx = Alist[0]
        tempAns = S - key * minx
        for a in Alist:
            tempAns2 = S2 - key * a
            if tempAns > tempAns2:
                tempAns = tempAns2
                minx = a
            S2 += - 2 * a
            key -= 2

        tempAns2 = S2 - key * a
        if tempAns > tempAns2:
            tempAns = tempAns2
            minx = a
        print(str(minx) + " " + str(tempAns+Bsum))

Submission status: Time Limit Exceeded

Solution code:
import bisect

def cul(a,b,n):
    if len(a)%2==1:
        ans=-sum(a[:n])+sum(a[n+1:])
    else:
        ans=-sum(a[:n+1])+sum(a[n+1:])
    return ans+b

q=int(input())
b=0
a=[]
for i in range(q):
    p=input()
    if p=="2":
        if len(a)%2==1:
            n=len(a)//2
            m=a[len(a)//2]
        else:
            n=len(a)//2-1
            m=a[len(a)//2-1]
        print(m,cul(a,b,n))
        
    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:
import bisect

Q = int(input())

A = []
B = 0

for _ in range(Q):
    q = input().split()
    if len(q)>1:
        __,a,b = map(int,q)
        i = bisect.bisect_left(A, a)
        A.insert(i, a)
        B += b
    else:
        i = (len(A)-1)//2
        a = A[i]
        s = B
        s += i*a - sum(A[:i])
        s += sum(A[i+1:]) - (len(A)-i-1)*a
        print(a, s)

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

aaa = []
len_aaa = 0
summ_diff = 0
summ_b = 0
min_x = 0
min_fx = 0
index_min_x=0
def update(a, b):
    global len_aaa
    global summ_b
    global min_x
    global min_fx
    global index_min_x
    global summ_diff



    bisect.insort_left(aaa, a)
    len_aaa += 1
    if len_aaa % 2 == 0:
        new_index_min_x = len_aaa//2 - 1
    else:
        new_index_min_x = len_aaa//2

    new_min_x = aaa[new_index_min_x]

    min_x_change = new_min_x - min_x

    summ_diff += abs(a - min_x)

    if len_aaa == 1:
        new_summ_diff = 0
    elif min_x_change > 0:
        new_summ_diff = summ_diff + ((new_index_min_x)*min_x_change) - ((len_aaa-new_index_min_x)*min_x_change)
    elif min_x_change < 0:
        new_summ_diff = summ_diff - ((new_index_min_x+1)*min_x_change) + ((len_aaa-new_index_min_x-1)*min_x_change)
    else:
        new_summ_diff = summ_diff


    summ_diff = new_summ_diff
    summ_b += b
    min_x = new_min_x
    index_min_x = new_index_min_x

    #print(index_min_x, min_x, min_x_change, summ_diff, summ_b)
    

def get_min_x():
    #print(str(min_x) + " " + str(f(min_x)))
    print(min_x, summ_diff+summ_b)

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
q = int(input())
a = []
b = 0
count = 0
for i in range(q):
    query = list(map(int,input().split()))
    if query[0] == 1:
        if len(a) == 0:
            a.append(query[1])
        else:
            insert_index = bisect_left(a,query[1])
            a.insert(insert_index,query[1])
        b += query[2]
        count += 1
    else:
        if count%2 == 1:
            x = a[count//2]
        else:
            x = a[count//2-1]
        ans = b
        for j in range(count):
            ans += abs(x-a[j])
        print(x,ans)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
num = []
fx = 0
for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        fx += query[2]
        num.append(query[1])
        num.sort()
        if len(num) % 2 == 1:
            minimum = num[len(num) // 2]
            ans = fx
            # print(ans)
            for n in range(len(num)):
                ans += abs(minimum - num[n])
            # print(ans)
        else:
            minimum = num[(len(num)//2) - 1]
            ans = fx
            # print(ans)
            for n in range(len(num)):
                ans += abs(minimum - num[n])
            # print(ans)
    elif query[0] == 2:
        print(str(minimum) + ' ' + str(ans))

Submission status: Time Limit Exceeded

Solution code:
import statistics
import numpy as np

num_q = int(input())
x = 0
f = 0
a = []
c = False

for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    a.append(n)
    if c:
      x_tmp = int(np.median(a + [-100000000]))
      f += m + np.abs(x - n)
    else:
      x_tmp = int(np.median(a))
      f += m + np.abs(x_tmp - n)
    c = ~c
    x = x_tmp

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
B = 0
for _ in range(N):
    query = list(map(int, input().split()))
    if query[0] == 1:
        A.append(query[1])
        B += query[2]
    else:
        A.sort()
        len_A = len(A)
        if len_A %2 == 0:
            A_sum = sum(A[int(len_A/2):]) - sum(A[:int(len_A/2)])
            print(A[int(len_A/2)-1], A_sum + B)
        else:
            A_sum = sum(A[int((len_A-1)/2):]) - sum(A[:int((len_A+1)/2)])
            print(A[int((len_A-1)/2)], A_sum + B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import insort_left

Q = int(input())

Data = []
lenD = 0
const = 0

def binaryInsert(a):
    insort_left(Data, a)

def getX():
    return Data[(lenD-1)//2]

def getMin():
    index = (lenD-1)//2
    return -sum(Data[:index])+sum(Data[index:])+(2*index-lenD)*getX()+const

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 2:
        print(getX(), getMin())
        continue
    a, b = query[1:]
    const += b
    binaryInsert(a)
    lenD += 1

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 len(query)==3:
        a.append(query[1])
        a.sort()
        b+=query[2]
    else:
        if len(a)%2==1:
            minx=a[int((len(a)-1)/2)]
            ans=b
            for j in range(len(a)):
                ans+=abs(minx-a[j])
            print(minx,ans)
        else:
            minx=a[int(len(a)/2)-1]
            ans=b
            for j in range(len(a)):
                ans+=abs(minx-a[j])
            print(minx,ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

ql=int(input())
es=[]
B=0
sumOfLefter = 0
sumOfRighter = 0
for qi in range(ql):
  q=tuple(map(int,input().split()))
  if q==(2,):
    re=B
    emidi = (len(es)-1)//2
    emid=es[emidi]
    for e in es:
      re += abs(e-emid)
    print(emid,re)
  else:
    e = q[1]
    b = q[2]
    ei = bisect.bisect_left(es,e)
    es.insert(ei,e)
    B+=b

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
Alist = []
S = 0
Bsum = 0
Qs = [input() for _ in range(Q)]
for query in Qs:
    if query[0] == "1":
        _, a, b = map(int, query.split(" "))
        Bsum += b
        Alist = sorted(Alist + [a, ])
        S += a
    else:
        key = len(Alist)
        S2 = S
        tempAns = S - key * Alist[0]
        minx = Alist[0]
        for a in Alist:
            tempAns2 = S2 - key * a
            if tempAns > tempAns2:
                tempAns = tempAns2
                minx = a
            S2 += - 2 * a
            key -= 2

        tempAns2 = S2 - key * a
        if tempAns > tempAns2:
            tempAns = tempAns2
            minx = a
        print(str(minx) + " " + str(tempAns+Bsum))

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q = int(input())

A = []
A_size = 0
A_med_min = 0
A_med_max = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        #常にソート済リストを作れる
        A.insert(bisect.bisect_left(A,a),a)
        A_size+=1
        #中央値との差分からA群からなる最小値を更新
        sabun = 0
        if a<A_med_min:
            sabun = A_med_min - a
        elif a>A_med_max:
            sabun = a - A_med_max
        MIN_SCORE += sabun + b if A_size>1 else b
        #中央値の更新
        if A_size%2==0:
            A_med_min = A[(A_size//2)-1]
            A_med_max = A[A_size//2]
        else:
            A_med_min = A[A_size//2]
            A_med_max = A[A_size//2]
    elif q[0]=="2":
        print(A_med_min,MIN_SCORE)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

a = list()
b = 0

for i in range(0,Q):
    query = list(map(int,input().split()))
    if query[0] == 1:
        a.append(query[1])
        b += query[2]
    else:
        a.sort()
        med = (len(a)-1)//2
        ans = b
        for i in range(0,len(a)):
           ans += abs(a[i]-a[med])
        print(a[med],ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import bisect
import math

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  Q = readInts()[0]
  points = []
  n = 0
  B = 0
  for _ in range(Q):
    query = readInts()
    if query[0] == 1:
      a, b = query[1], query[2]
      bisect.insort(points, a)
      n += 1
      B += b
    else:
      med = points[math.floor((n - 1) / 2)]
      ans = B
      for i in range(n):
        ans += abs(med - points[i])
      print("{} {}".format(med, ans))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def solve(a,b):
    x = a[0]
    f = sum(list(map(lambda y:abs(y-x) ,a)))+b
    for i in range(a[0]+1,a[-1]):
        if f >  sum(list(map(lambda y:abs(y-x) ,a))) + b:
            x = i
            f =  sum(list(map(lambda y:abs(y-x) ,a)))+b
    print(x,f)


for i in range(n):
    q = input()
    if q[0] == '2':
        solve(a,b)
    else:
        n,a_,b_ = [int(x) for x in q.split()]
        a.append(a_)
        a.sort()
        b += b_

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import bisect
q=int(input())
h=[]
l=0 #hの要素数
b=0 #bの和
s=0 #絶対偏差の和
med=0
for _ in range(q):
    Tmp=list(map(int,input().split()))
    if Tmp[0]==1:
        b+=Tmp[2]
        if l%2:
            s+=abs(Tmp[1]-med)
        else:
            if l:
                med_next=h[(l-1)//2+1]
                if Tmp[1]<=med:
                    s+=abs(Tmp[1]-med)
                elif Tmp[1]>=med_next:
                    s+=abs(Tmp[1]-med_next)                
        l+=1
        bisect.insort(h,Tmp[1])
        med=h[(l-1)//2]
    else:
        print(med,s+b)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect

def main():
    q = II()
    Q = []
    for _ in range(q):
        Q.append(LI())
    A = []
    bias = 0
    for q in Q:
        if q == [2]:
            idx = (len(A) - 1) // 2
            ans = A[idx], (sum(A[len(A) - idx - 1:]) - sum(A[:idx + 1]) + bias)
            print(*ans)
        else:
            _, a, b = q
            bias += b
            index = bisect(A, a)
            A.insert(index, a)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import bisect

Q = int(input())

A = []
B = 0
for _ in range(Q):
    inp = list(map(int,input().split()))
    if inp[0] == 1:
        
        index = bisect.bisect_left(A, inp[1])
        A.insert(index, inp[1])
        B += inp[2]

    elif inp[0] == 2:
        l = len(A)
        if l == 0:
            print(0,0)
        else:
            index = (l+1)//2 - 1
            x = A[index]
            s = x * (2*index + 2 - l) - sum(A[0: index+1]) + sum(A[index+1:])
            print(x, s + B)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bs

a = []
l = 0
sum0 = 0
sum1 = 0

b = 0
for i in range(int(input())):
  z = list(map(int,input().split()))
  if z[0] == 2:
    if l%2 == 0:
      t = a[l//2-1]
      #print("memo",a,b,l,t,sum0,sum1)
      print(str(t)+" "+str(sum1-sum0+b))
    else:
      t = a[l//2]
      #print("memo",a,b,l,t,sum0,sum1)
      print(str(t)+" "+str(sum1-sum0+t+b))
  else:
    b += z[2]
    k = z[1]
    i = bs.bisect_left(a,k)
    if l%2 == 0:
      if i <= l//2:
        sum0 += k
      else:
        t = a[l//2]
        sum0 += t
        sum1 += k - t
    else:
      if i < l//2+1:
        t = a[l//2]
        sum0 += k - t
        sum1 += t
      else:
        sum1 += k      
    a.insert(i,k)
    l += 1


#print(a)
#print(b)
#print(sum0,sum1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

ql=int(input())
es=[]
B=0
for qi in range(ql):
  q=tuple(map(int,input().split()))
  if q==(2,):
    re=B
    if len(es)%2==0:
      ei=len(es)//2-1
    else:
      ei=(len(es)-1)//2
    emin=es[ei]
    for e in es:
      re += abs(e-emin)
    print(emin,re)
  else:
    e = q[1]
    b = q[2]
    ei = bisect.bisect_left(es,e)
    es.insert(ei,e)
    es.sort()
    B+=b

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()


class WHeap(object):
    def __init__(self):
        self._heap1 = []
        self._heap2 = []

    def __len__(self):
        return len(self._heap1) + len(self._heap2)

    def iter(self):
        for i in self._heap1:
            yield -i
        for i in self._heap2:
            yield i

    def __str__(self):
        return str(self._heap1) + " " + str(self._heap2)

    def push(self, n):
        if len(self) % 2 == 0:
            if not self._heap2 or n <= self._heap2[0]:
                heapq.heappush(self._heap1, -n)
            else:
                heapq.heappush(self._heap1, -heapq.heappop(self._heap2))
                heapq.heappush(self._heap2, n)
        else:
            if n < -self._heap1[0]:
                heapq.heappush(self._heap2, -heapq.heappop(self._heap1))
                heapq.heappush(self._heap1, -n)
            else:
                heapq.heappush(self._heap2, n)

    def med(self):
        return -self._heap1[0]

    def pop(self, n):
        result = self.med()
        if len(self) % 2 == 0:
            heapq.heappop(self._heap1)
            heapq.heappush(self._heap1, -heapq.heappop(self._heap2))
        else:
            heapq.heappop(self._heap1)


def main():
    Q = II()
    wh = WHeap()
    B = 0
    for _ in range(Q):
        query = MIT()
        if query[0] == 1:
            wh.push(query[1])
            B += query[2]
        else:
            x = wh.med()
            f = sum(map(lambda i: abs(x - i), wh.iter())) + B
            print(x, f)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import factorial as f
from fractions import gcd as g

Q = int(raw_input ())
C = []
c = 0
X = 0

def solve():
    if len(C) == 0: return c
    x = X // len(C)
    return (x, c + sum(abs(x - i) for i in C))


for i in range(Q):
    l = [int(i) for i in raw_input ().split()]
    if len(l) == 1:
        if len(C) % 2 == 0:
            N = len(C)
            sum = c
            for j in range(N / 2, N):
                sum += C[j]
            for j in range(N / 2):
                sum -= C[j]
            print C[N / 2 - 1], sum
        else:
            N = len(C)
            sum = c
            for j in range(N / 2 + 1, N):
                sum += C[j]
            for j in range(N / 2):
                sum -= C[j]
            print C[N / 2], sum
        # x, y = solve()
        # print x, y
    else:
        c += l[-1]
        C.append(l[1])
        C.sort()
        # print C

Submission status: Time Limit Exceeded

Solution code:
import statistics

q=int(input())
a=[]
len_a=0
sum_b=0
for _ in range(q):
    qi=list(map(int,input().split()))
    if qi[0]==1:
        a.append(qi[1])
        sum_b+=qi[2]
        len_a+=1
    else:
        m=statistics.median_low(a)
        print(m,sum_b+sum(abs(x-m) for x in a))

Submission status: Time Limit Exceeded

Solution code:
import statistics
import numpy as np

num_q = int(input())
x = 0
f = 0
a = []
c = False

for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    a.append(n)
    x_tmp = statistics.median_low(a)
    if c:
      f += m + np.abs(x - n)
    else:
      f += m + np.abs(x_tmp - n)
    c = ~c
    x = x_tmp

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input = sys.stdin.readline
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:
    n=bisect.bisect_left(A,L[1])
    A.insert(n,L[1])
    b+=L[2]
  else:
    n=A[(len(A)-1)//2]
    print(n,f(A,b,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
rr = lambda: sys.stdin.readline().strip()
rri = lambda: int(rr())
rrs = lambda: [int(_) for _ in rr().split()]

from bisect import insort_left

Q = rri()
avg = 0
a = []
b = 0
c = 0

for _ in range(Q):
    d = rrs()

    if d[0] == 1:
        insort_left(a, d[1])
        b += d[2]
        c = len(a)
        m = -(-c//2)-1
    
    if d[0] == 2:
        ans = b
        for i in range(c):
            ans += abs(a[m] - a[i])
        print(a[m], ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q = int(input())

A = []
B = 0

for _ in range(Q):
    q = input().split()
    if len(q)>1:
        __,a,b = map(int,q)
        i = bisect.bisect_left(A, a)
        A.insert(i, a)
        B += b
    else:
        a = A[(len(A)-1)//2]
        s = B
        for x in A:
            s += abs(x-a)
        print(a, s)

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        a.append(q[1])
        b += q[2]
    else:
        a.sort()
        idx = len(a) // 2
        if len(a) % 2 == 0:
            ans_x = a[idx-1]
        else:
            ans_x = a[idx]
        ans = b
        if len(a) == 0:
            print("0 0")
        else:
            for v in a:
                if v < ans_x:
                    ans += ans_x - v
                else:
                    ans += v - ans_x
            print("{0} {1}".format(ans_x, ans))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc127/tasks/abc127_f
import bisect
import sys

Q = int(input())
offset = 0
xs = []
for _ in range(Q):
    query = input()
    if query[0] == "1":
        a, b = map(int, query[1:].split())
        offset += b
        idx = bisect.bisect_right(xs, a)
        xs.insert(idx, a)
        # print(xs, file=sys.stderr)
    else:
        x = xs[(len(xs) - 1) // 2]
        y = offset + sum(abs(x - xp) for xp in xs)
        print(x, y)

Submission status: Time Limit Exceeded

Solution code:
import bisect
Q=int(input())
A=[]
B=0
for i in range(Q):
  S=input()
  if S[0]=="1":
    a,b=map(int,S[2:].split())
    bisect.insort_left(A,a)
    B+=b
  else:
    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 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:
        A.sort()
        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:
# -*- coding: utf-8 -*-

import bisect
import math

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  Q = readInts()[0]
  points = [None for _ in range(Q)]
  n = 0
  B = 0
  for _ in range(Q):
    query = readInts()
    if query[0] == 1:
      a, b = query[1], query[2]
      bisect.insort(points, a, lo=0, hi=n)
      n += 1
      B += b
    else:
      med = points[math.floor((n - 1) / 2)]
      ans = B
      for i in range(n):
        ans += abs(med - points[i])
      print("{} {}".format(med, ans))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, bsum, c = [], 0, 0
for query in queries:
    if query[0] == '2':
        absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        bsum += b
        c += 1

Submission status: Time Limit Exceeded

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


import statistics


def main():
    q = int(input())
    alphas = []
    sum_betas = 0
    for _ in range(q):
        rs = [int(x) for x in input().split()]
        if rs[0] == 1:
            alpha, beta = rs[1:]
            alphas.append(alpha)
            sum_betas += beta
        else:
            med = statistics.median_low(alphas)
            res = sum(abs(med - alpha) for alpha in alphas) + sum_betas
            print(med, res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
q = int(input())

queries = [[int(i) for i in input().split()] for j in range(q)]

a_l = []
b_sum = 0
for query in queries:
    if query[0] == 1:
        a, b = query[1:]
        i = bisect.bisect_left(a_l, a)
        a_l.insert(i, a)
        b_sum += b
        x = a_l[(len(a_l) - 1) // 2]
    else:
        print(x, sum([abs(x - a_i) for a_i in a_l]) + b_sum)

Submission status: Time Limit Exceeded

Solution code:
q = int(raw_input())

list_a = []
sum_b = 0

for i in range(0, q):
    inp = map(int, raw_input().split(" "))

    if len(inp) == 3:  # 1
        a = inp[1]
        b = inp[2]
        list_a.append(a)
        sum_b += b

    else: # 2
        sort = sorted(list_a)
        if len(list_a) % 2 == 0:
            index = len(list_a) / 2 - 1
        else:
            index = int(len(list_a) / 2)

        #print("%d %d" % (len(sort), index))
        min_x = sort[index]

        temp_sum = 0
        for j in range(0, len(sort)):
            temp_sum += abs(min_x - sort[j])

        print("%d %d" % (min_x, temp_sum + sum_b))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())

a_lst = []
b = 0
drift = 0
center = 0
for i in range(N):
	vals = list(map(int,input().split()))
	if len(vals) == 3:
		if i == 0:
			drift = 0
		elif len(a_lst)%2 == 0:
			center_1 = a_lst[(len(a_lst)//2)-1]
			center_2 = a_lst[(len(a_lst)//2)]
			if vals[1] < center_1:
				drift += center_1 - vals[1]
			elif vals[1] > center_2:
				drift += vals[1] - center_2
			# if new point in between center. drift is not increase
			
		else:
			drift += abs(vals[1]-center)
		
		index = bisect.bisect_left(a_lst, vals[1])
		a_lst.insert(index, vals[1])
		
		center = a_lst[(len(a_lst)-1)//2]
		b += vals[2]
	else:
		print(center,drift + b)