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 sys,heapq
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
ddprint("q " + str(q))
for i in range(1,q):
    #ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            aa = -heapq.heappushpop(tl,-a)
            suml += a - aa
            if aa<root:
                aa,root = root,aa
            heapq.heappush(tr,aa)
            sumr += aa
            nr += 1
        else:
            aa = heapq.heappushpop(tr,a)
            sumr += a - aa
            if aa>root:
                aa,root = root,aa
            heapq.heappush(tl,-aa)
            suml += aa
            nl += 1
        #ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        #ddprint(tl)
        #ddprint(tr)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
ddprint("q " + str(q))
for i in range(1,q):
    #ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            heapq.heappush(tl,-a)
            suml += a
            a = -heapq.heappop(tl)
            suml -= a
            if a<root:
                a,root = root,a
            heapq.heappush(tr,a)
            sumr += a
            nr += 1
        else:
            heapq.heappush(tr,a)
            sumr += a
            a = heapq.heappop(tr)
            sumr -= a
            if a>root:
                a,root = root,a
            heapq.heappush(tl,-a)
            suml += a
            nl += 1
        #ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        #ddprint(tl)
        #ddprint(tr)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
ddprint("q " + str(q))
for i in range(1,q):
    ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            heapq.heappush(tl,-a)
            suml += a
            a = -heapq.heappop(tl)
            suml -= a
            if a<root:
                a,root = root,a
            heapq.heappush(tr,a)
            sumr += a
            nr += 1
        else:
            heapq.heappush(tr,a)
            sumr += a
            a = heapq.heappop(tr)
            sumr -= a
            if a>root:
                a,root = root,a
            heapq.heappush(tl,-a)
            suml += a
            nl += 1
        ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        ddprint(tl)
        ddprint(tr)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    q = I()
    aa = [LI() for _ in range(q)]

    bt = aa[0][2]
    m = 2 ** 20
    x = [-inf * m + 1, aa[0][1] * m + 1, inf * m + 1]
    xi = 1
    xl = 0
    lc = 0
    xr = 0
    rc = 0
    r = []
    for t in aa[1:]:
        if t[0] == 2:
            r.append('{} {}'.format(x[xi] // m, xl+xr+bt))
        else:
            _,a,b = t
            bt += b
            xt = x[xi]
            xa = xt // m
            xc = xt % m
            if xa == a:
                x[xi] += 1
                continue
            bi = bisect.bisect_left(x, a * m)
            if x[bi] // m == a:
                x[bi] += 1
            else:
                if bi <= xi:
                    xi += 1
                x.insert(bi, a * m + 1)
            if bi < xi:
                xl += xa - a
                lc += 1
                t = xl + xr
                nt = x[xi-1]
                na = nt // m
                nc = nt % m
                s = xa - na
                nt = xl - lc * s + xr + (rc+xc) * s
                if nt <= t:
                    xl -= lc * s
                    xr += (rc+xc) * s
                    lc -= nc
                    rc += xc
                    xi -= 1
            else:
                xr += a - xa
                rc += 1
                t = xl + xr
                nt = x[xi+1]
                na = nt // m
                nc = nt % m
                s = na - xa
                nt = xl + (lc+xc) * s + xr - rc * s
                if nt < t:
                    xl += (lc+xc) * s
                    xr -= rc * s
                    lc += xc
                    rc -= nc
                    xi += 1

    return '\n'.join(r)


print(main())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import copy

q = int(input())
a = []
b = 0
for i in range(q):
  x = list(map(int, input().split()))
  if x[0] == 1:
    heappush(a, x[1])
    b += x[2]
  else:
    c = copy.deepcopy(a)
    for i in range((len(c) + 1) // 2):
      med = heappop(c)
    print(med, sum([abs(y - med) for y in a]) + b)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
INF = 10 ** 9

from bisect import insort_left

ary, absum, bsum, c = [], 0, 0, 0
left, right = -INF, INF
for _ in range(Q):
    query = input()
    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))))
        print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        c += 1
        if left <= a <= right:
            absum += 0
        elif a < left:
            absum += left - a
        else:
            absum += a - right
        left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
Q = int(input())
n, a, b = map(int, input().split())
mi = b
L = [-a]
R = [a]
num = 1
for i in range(Q - 1):
    q = list(map(int, input().split()))
    if len(q) == 3:
        if num % 2 != 0:
            l = -heappop(L)
            r = heappop(R)
            l1 = min(l, q[1])
            r1 = max(r, q[1])
            heappush(L, -l1)
            heappush(R, r1)
            mi += abs(l - q[1])
        else:
            if q[1] < -L[0]:
                heappush(L, -q[1])
                heappush(R, -L[0])
                mi -= q[1] + L[0]
            elif q[1] > R[0]:
                heappush(L, -R[0])
                heappush(R, q[1])
                mi += q[1] - R[0]
            else:
                heappush(L, -q[1])
                heappush(R, q[1])

        mi += q[2]
        num += 1
    else:
        print(-L[0], mi)

Submission status: Time Limit Exceeded

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

import sys
from bisect import insort_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

Q=INT()

li=[]
A=B=fx=cost=cnt=l=r=0
for _ in range(Q):
    instr=input()
    if instr[0]=='1':
        _,a,b=map(int, instr.split())
        B+=b
        insort_left(li, a)
        if cnt==0:
            l=r=A=a
        else:
            if not (l<=a<=r):
                cost+=min(abs(l-a), abs(r-a))
            # 偶数回目
            if cnt%2==1:
                A=l=li[len(li)//2-1]
                r=li[len(li)//2]
            # 奇数回目
            else:
                A=l=r=li[len(li)//2]
        fx=cost+B
        cnt+=1
    else:
        print(A, fx)

Submission status: Time Limit Exceeded

Solution code:
import bisect
Q = int(input())
a_list, b_list = [], []
a_arr = []
fs = []
def f(x): return 0

for _ in range(Q):
  q = input()
  if q.startswith('1'):
    temp, a, b = map(int, q.split())
    a_list.append(a)
    b_list.append(b)
    bisect.insort(a_arr, a)
    def f(x):
      y = sum([abs(x - a) + b for a, b in zip(a_list, b_list)])
      return y
    
  else:
    mina = a_arr[(len(a_arr) - 1)//2]
    minf = f(mina)
    print(mina, minf)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

def foo(x):
    sum = 0
    for y in a:
        sum += abs(y-x)
    return sum+b

a = []
b = 0
q = inn()
for i in range(q):
    x = inl()
    if len(x)==1:
        z = (len(a)-1)//2
        print("{} {}".format(a[z],foo(a[z])))
    else:
        z = x[1]
        if len(a)==0 or a[-1] <= z:
            a.append(z)
        elif z <= a[0]:
            a.insert(0,z)
        else:
            up = len(a)-1
            lo = 0
            while lo+1 < up:
                mid = (lo+up)//2
                if z < a[mid]:
                    up = mid
                else:
                    lo = mid
            a.insert(up,z)
        b += x[2]

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

def foo(x):
    sum = 0
    for y in a:
        sum += abs(y-x)
    return sum+b

a = []
b = 0
q = inn()
for i in range(q):
    x = inl()
    if len(x)==1:
        z = (len(a)-1)//2
        print("{} {}".format(a[z],foo(a[z])))
    else:
        a.append(x[1])
        a.sort()
        b += x[2]

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import statistics
import math
import re

def main(params):
    q = params[0]
    queries = params[1:]
    currentB = 0
    currentA = 0
    listA = []
    for i in queries:
        line = i.split()
        if len(line) > 1:
            code, a, b = [int(j) for j in i.split()]
            currentB += b
            listA.append(a)
            target = len(listA)/2
            if len(listA) % 2 == 0:
                target = statistics.median_low(listA)
                target2 = statistics.median_high(listA)
                if a <= target:
                    currentA += abs(a - target) + abs(target - target2)
                elif a >= target2:
                    currentA += abs(a - target2) + abs(target - target2)
            else:
                target = statistics.median(listA)
                currentA += abs(a - target)
        else:
            if len(listA) % 2 == 0:
                target = statistics.median_low(listA)
            else:
                target = statistics.median(listA)
            print (target, currentA + currentB)

if __name__ == "__main__":
    q = input()
    q = int(q)
    cnt = q # TODO: edit here
    params = [q]
    for i in range(cnt):
        param = input()
        params.append(param)
    main(params)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
 
import math
import re
 
def main(params):
    q = params[0]
    queries = params[1:]
    currentB = 0
    currentA = 0
    listA = []
    for i in queries:
        line = i.split()
        if len(line) > 1:
            code, a, b = [int(j) for j in i.split()]
            currentB += b
            listA.append(a)
            listA.sort()
            target = len(listA)/2
            if len(listA) % 2 == 0:
                if a <= listA[target-1]:
                    currentA += abs(a - listA[target-1]) + abs(listA[target-1] - listA[target])
                elif a >= listA[target]:
                    currentA += abs(a - listA[target]) + abs(listA[target-1] - listA[target])
            else:
                currentA += abs(a - listA[target])
        else:
            target = len(listA)/2
            if len(listA) % 2 == 0:
                target -= 1
            print listA[target], currentA + currentB
#            listA.sort()
#            target = len(listA)/2
#            if len(listA) % 2 == 0:
#                target -= 1
#            t = 0
#            for j in listA:
#                t += abs(listA[target] - j)
#            t += currentB
#            print listA[target],t
 
 
if __name__ == "__main__":
    q = raw_input()
    q = int(q)
    cnt = q # TODO: edit here
    params = [q]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
INF = 10 ** 9

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

from bisect import insort_left

ary, absum, bsum, c = [], 0, 0, 0
left, right = -INF, INF
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))))
        print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        c += 1
        if left <= a <= right:
            absum += 0
        elif a < left:
            absum += left - a
        else:
            absum += a - right
        left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(1,L)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  q = [int(x) for x in input().split()]
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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:
        summ_diff = 0
    elif min_x_change > 0:
        summ_diff += ((new_index_min_x*2 - len_aaa)*min_x_change)
    else:
        summ_diff -= ((2*new_index_min_x - len_aaa + 2)*min_x_change)

    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"):
    if s[0] == "1":
        a,b = map(int, s[2:].split(" "))
        update(a, b)
    else:
        get_min_x()

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:
        summ_diff = 0
    elif min_x_change > 0:
        summ_diff += ((new_index_min_x*2 - len_aaa)*min_x_change)
    else:
        summ_diff -= ((2*new_index_min_x - len_aaa + 2)*min_x_change)

    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(" "))
        update(a, b)
    else:
        get_min_x()

Submission status: Time Limit Exceeded

Solution code:
import bisect
Q=int(input())
alist=[]
b=0
cnt=0
for _ in range(Q):
    s=input()
    if s[0]=='1':
        cnt+=1
        _,ra,rb=map(int, s.split())
        insert_index=bisect.bisect_left(alist, ra)
        alist.insert(insert_index, ra)
        b+=rb
    if s[0]=='2':
        index = int((cnt+1)/2)-1
        if cnt % 2 == 0:
            print(alist[index], -sum(alist[:index])+sum(alist[index+1:])-alist[index]+b)
        if cnt % 2 == 1:
            print(alist[index], -sum(alist[:index])+sum(alist[index+1:])+b)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

import heapq

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -L[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(1,L)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

QUERY = [[int(x) for x in input().split()] for _ in range(Q)]
for q in QUERY:
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(1,L)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
INF = 10 ** 9

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

from bisect import insort_left

ary, absum, bsum, c = [], 0, 0, 0
left, right = -INF, INF
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)
        c += 1
        if left <= a <= right:
            absum += 0
        elif a < left:
            absum += left - a
        else:
            absum += a - right
        left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

import heapq

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(1,L)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import math
import re

def main(params):
    q = params[0]
    queries = params[1:]
    currentB = 0
    currentA = 0
    listA = []
    for i in queries:
        line = i.split()
        if len(line) > 1:
            code, a, b = [int(j) for j in i.split()]
            currentB += b
            listA.append(a)
            listA.sort()
            target = len(listA)/2
            if len(listA) % 2 == 0:
                if a <= listA[target-1]:
                    currentA += abs(a - listA[target-1]) + abs(listA[target-1] - listA[target])
                elif a >= listA[target]:
                    currentA += abs(a - listA[target]) + abs(listA[target-1] - listA[target])
            else:
                currentA += abs(a - listA[target])
        else:
            target = len(listA)/2
            if len(listA) % 2 == 0:
                target -= 1
            print listA[target], currentA + currentB
#            listA.sort()
#            target = len(listA)/2
#            if len(listA) % 2 == 0:
#                target -= 1
#            t = 0
#            for j in listA:
#                t += abs(listA[target] - j)
#            t += currentB
#            print listA[target],t


if __name__ == "__main__":
    q = raw_input()
    q = int(q)
    cnt = q # TODO: edit here
    params = [q]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Time Limit Exceeded

Solution code:
import bisect

def getlist():
	return list(map(int, input().split()))

Q = int(input())
A = []
B = 0
n = 1

f, a, b = getlist()
bisect.insort_left(A, a)
B += b
ans1 = 0
for i in range(Q - 1):
	x = getlist()
	if x[0] == 1:
		a, b = x[1], x[2]
		if n % 2 == 0:
			u, v = A[int(n // 2) - 1], A[int(n // 2)]
			if a <= u:
				ans1 += u - a
			elif a >= v:
				ans1 += a - v

		else:
			ans1 += abs(A[int((n + 1) // 2) - 1] - a)
		bisect.insort_left(A, a)
		B += b
		n += 1

	else:
		if n % 2 == 0:
			X = A[int(n // 2) - 1]
		else:
			X = A[int((n + 1) // 2) - 1]
		print(X, ans1 + B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 25 21:57:15 2019

@author: Yamazaki Kenichi
"""
import bisect

Q = int(input())
Q2 = [input() for i in range(Q)]

ans = []
A = []
B = 0
C = 0
counta = 0
d, prea, b = map(int,Q2[0].split()) 
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split()) 
        bisect.insort_left(A,a)
#        if A[(len(A)-1)//2] > a:
#            C = abs(prea - a)
#        else:
#            C = abs(A[(len(A)-1)//2] - a)
        C = abs(A[(len(A)-1)//2] - a) if counta % 2 == 0 else abs(prea - a)
        B += (b + C)
#        C = abs(prea - a)
        prea = A[(len(A)-1)//2]
        counta += 1
    else:
#        output
        tmp = A[(len(A)-1)//2]
        ans.append([tmp,B])
for c in ans:
    print(' '.join(map(str,c)))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import numpy as np
 
num_q = int(input())
x = 0
f = 0
low = []
high = []
odd = False
num_a = 0
 
for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    if odd:
      if n >= -low[0]:
        heappush(high, n)
      else:
        heappush(low, -n)
        heappush(high, -heappop(low))
    else:
      if num_a and n > -low[0]:
        heappush(high, n)
        heappush(low, -heappop(high))
      else:
        heappush(low, -n)

    x_tmp = -low[0]
    if odd:
      f += m + np.abs(x - n)
    else:
      f += m + np.abs(x_tmp - n)

    odd = ~odd
    x = x_tmp
    num_a += 1

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop
L,R=[],[]
n=1
heapify(L)
heapify(R)
Q=int(input())
s,a,b=map(int,input().split())
heappush(L,-a)
S_L,S_all=a,a
for q in range(Q-1):
  q_=[int(i) for i in input().split()]
  if q_[0]==1:
    a,b_=q_[1],q_[2]
    b+=b_
    if n%2==0:
      if a<=R[0]:
        heappush(L,-a)
        S_L+=a
        S_all+=a
      else:
        k=heappop(R)
        S_L+=k
        S_all+=a
        heappush(L,-k)
        heappush(R,a)
    else:
      if a>=-L[0]:
        heappush(R,a)
        S_all+=a
      else:
        k=-heappop(L)
        S_L+=a-k
        S_all+=a
        heappush(R,k)
        heappush(L,-a)
    n+=1
  if q_[0]==2:
    if n%2==0:
      print(-L[0],-S_L+(S_all-S_L)+b)
    else:
      print(-L[0],-S_L-L[0]+(S_all-S_L)+b)