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 numpy as np
import heapq
Q = int(input())
Qinit = list(map(int,input().split()))
Qlist = [list(map(int,input().split())) for i in range(Q-1)]

#coef_list = []
intercept = Qinit[2]
left_list = []
cent_list = [Qinit[1]]
right_list = []
left_sum = 0
right_sum = 0

median = Qinit[1]
count = [0,0]

for query in Qlist:
    if query[0] == 1:
        source = query[1]
        intercept += query[2]

        if cent_list == []:
            if median > source:
                heapq.heappush(left_list, -source)
                left_sum += source #
                tmp = -heapq.heappop(left_list)
                left_sum -= tmp #
                cent_list.append(tmp)
            elif right_list[0] > source:
                cent_list.append(source)
            else:
                heapq.heappush(right_list, source)
                tmp = heapq.heappop(right_list)
                right_sum += source - tmp
                cent_list.append(tmp)
            median = cent_list[0]
        else:
            if cent_list[0] < source:
                heapq.heappush(left_list, -cent_list[0])
                count[0] += 1
                left_sum += cent_list[0]
                median = cent_list[0]
                heapq.heappush(right_list, source)
                count[1] += 1
                right_sum += source
                cent_list.remove(cent_list[0])
            else:
                heapq.heappush(left_list, -source)
                left_sum += source
                count[0] += 1
                median = -left_list[0]
                heapq.heappush(right_list, cent_list[0])
                count[1] += 1
                right_sum += cent_list[0]
                cent_list.remove(cent_list[0])

    else:
        cent = 0
        if cent_list != []:
            cent = cent_list[0]
        minval = np.abs(left_sum-count[0]*median) + np.abs(right_sum-count[1]*median)
        minval += intercept
        print(str(median) + " " + str(minval))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
Q = int(input())
Qinit = list(map(int,input().split()))
Qlist = [list(map(int,input().split())) for i in range(Q-1)]

#coef_list = []
intercept = [Qinit[2]]
left_list = []
cent_list = [Qinit[1]]
right_list = []
left_sum = [0]
right_sum = [0]

median = [Qinit[1]]
count = [0,0]

def update_func(query):
    source = query[1]
    #coef_list.append(query[1])
    intercept[0] += query[2]
    """
    if len(coef_list) == 1:
        cent_list.append(source)
        median[0] = cent_list[0]
        return
    """
    if cent_list == []:
        if median[0] > source:
            heapq.heappush(left_list, -source)
            left_sum[0] += source #
            tmp = -heapq.heappop(left_list)
            left_sum[0] -= tmp #
            cent_list.append(tmp)
        elif right_list[0] > source:
            cent_list.append(source)
        else:
            heapq.heappush(right_list, source)
            tmp = heapq.heappop(right_list)
            right_sum[0] += source - tmp
            cent_list.append(tmp)
        median[0] = cent_list[0]
    else:
        if cent_list[0] < source:
            heapq.heappush(left_list, -cent_list[0])
            count[0] += 1
            left_sum[0] += cent_list[0]
            median[0] = cent_list[0]
            heapq.heappush(right_list, source)
            count[1] += 1
            right_sum[0] += source
            cent_list.remove(cent_list[0])
        else:
            heapq.heappush(left_list, -source)
            left_sum[0] += source
            count[0] += 1
            median[0] = -left_list[0]
            heapq.heappush(right_list, cent_list[0])
            count[1] += 1
            right_sum[0] += cent_list[0]
            cent_list.remove(cent_list[0])
    return
def solve_func():
    cent = 0
    if cent_list != []:
        cent = cent_list[0]
    minval = np.abs(left_sum[0]-count[0]*median[0]) + np.abs(right_sum[0]-count[1]*median[0])
    minval += intercept[0]
    print(str(median[0]) + " " + str(minval))

for query in Qlist:
    if query[0] == 1:
        update_func(query)
    else:
        solve_func()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
Q = int(input())
Qlist = [list(map(int,input().split())) for i in range(Q)]
#print(Qlist)
coef_list = []
intercept = [0]
left_list = []
cent_list = []
right_list = []
left_sum = [0]
right_sum = [0]

median = [0]
count = [0,0]

def update_func(query):
    source = query[1]
    coef_list.append(query[1])
    intercept[0] += query[2]

    if len(coef_list) == 1:
        cent_list.append(source)
        median[0] = cent_list[0]
        return
    if cent_list == []:
        if median[0] > source:
            heapq.heappush(left_list, -source)
            left_sum[0] += source #
            tmp = -heapq.heappop(left_list)
            left_sum[0] -= tmp #
            cent_list.append(tmp)
        elif right_list[0] > source:
            cent_list.append(source)
        else:
            heapq.heappush(right_list, source)
            tmp = heapq.heappop(right_list)
            right_sum[0] += source - tmp
            cent_list.append(tmp)
        median[0] = cent_list[0]
    else:
        if cent_list[0] < source:
            heapq.heappush(left_list, -cent_list[0])
            count[0] += 1
            left_sum[0] += cent_list[0]
            median[0] = cent_list[0]
            heapq.heappush(right_list, source)
            count[1] += 1
            right_sum[0] += source
            cent_list.remove(cent_list[0])
        else:
            heapq.heappush(left_list, -source)
            left_sum[0] += source
            count[0] += 1
            median[0] = -left_list[0]
            heapq.heappush(right_list, cent_list[0])
            count[1] += 1
            right_sum[0] += cent_list[0]
            cent_list.remove(cent_list[0])
    return
def solve_func():
    cent = 0
    if cent_list != []:
        cent = cent_list[0]
    minval = np.abs(left_sum[0]-count[0]*median[0]) + np.abs(right_sum[0]-count[1]*median[0])
    minval += intercept[0]
    print(str(median[0]) + " " + str(minval))

for query in Qlist:
    if query[0] == 1:
        update_func(query)
    else:
        solve_func()

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math

Q = int(input())
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))

a_list = []
b_sum = 0
a_sum = 0
a_sum_half = 0
for i in range(Q):
	if len(q[i]) == 3:
		loc = bisect.bisect(a_list, q[i][1])
		bisect.insort(a_list, q[i][1])
		length = len(a_list)
		if length % 2 == 0 and loc < length//2:
			a_sum_half += q[i][1]
		elif length % 2 == 0 and loc >= length//2:
			a_sum_half += a_list[length//2 - 1]
		elif length % 2 == 1 and loc < length // 2:
			a_sum_half += q[i][1]
			a_sum_half -= a_list[length//2]
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		index = (length - 1)//2
		argmin_x = a_list[index]
		min_x = argmin_x*(length//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(length - length//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math

Q = int(input())
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))

a_list = []
b_sum = 0
a_sum = 0
a_sum_half = 0
for i in range(Q):
	if len(q[i]) == 3:
		loc = bisect.bisect(a_list, q[i][1])
		bisect.insort(a_list, q[i][1])
		if len(a_list) % 2 == 0 and loc < len(a_list)//2:
			a_sum_half += q[i][1]
		elif len(a_list) % 2 == 0 and loc >= len(a_list)//2:
			a_sum_half += a_list[len(a_list)//2 - 1]
		elif len(a_list) % 2 == 1 and loc < len(a_list) // 2:
			a_sum_half += q[i][1]
			a_sum_half -= a_list[len(a_list)//2]
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		index = (len(a_list) - 1)//2
		argmin_x = a_list[index]
		min_x = argmin_x*(len(a_list)//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(len(a_list) - len(a_list)//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


class median_o1:
    def __init__(self):
        self.count = 0
        self.al = []
        self.ar = []
        self.sl = 0
        self.sr = 0
        self.b = 0

    def update_b(self, b):
        self.b += b

    def insert(self, x):
        if self.count % 2 == 0:
            if self.count == 0:
                heappush(self.al, -x)
                self.sl += x
            else:
                t = heappop(self.ar)
                self.sr -= t
                tl, tr = min(x, t), max(x, t)
                heappush(self.al, -tl)
                self.sl += tl
                heappush(self.ar, tr)
                self.sr += tr
        else:
            t = heappop(self.al)
            t *= (-1)
            self.sl -= t
            tl, tr = min(x, t), max(x, t)
            heappush(self.ar, tr)
            self.sr += tr
            heappush(self.al, -tl)
            self.sl += tl
        self.count += 1

    def get_median(self):
        return -self.al[0]

    def calc_min_value(self):
        # print(self.al, self.ar, self.b, self.sl, self.sr)
        m = self.get_median()
        return (m * ((self.count + 1) // 2) - self.sl) + (self.sr - m * (self.count // 2)) + self.b


q = int(input())

m = median_o1()

for _ in range(q):
    q_typ, *x = tuple(map(int, input().split()))
    # 1, [a, b]
    # 2, []
    if q_typ == 1:
        m.update_b(x[1])
        m.insert(x[0])
    else:
        print(m.get_median(), m.calc_min_value())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
def resolve():
    N = int(input())
    b = 0
    left = []
    right = []
    sumleft = sumright = mid = 0
    for _ in range(N):
        q = list(map(int,input().split()))
        if q[0]==1:#登録
            a = q[1]
            b = b + q[2]
            if not left or -left[0]>a:
                heappush(left,-a)
                sumleft = sumleft + a
                if (len(left)-len(right))>=2:
                    move = -heappop(left)
                    heappush(right,move)
                    sumleft = sumleft-move
                    sumright = sumright+move
            else:
                heappush(right,a)
                sumright = sumright + a
                if len(left)<len(right):
                    move = heappop(right)
                    heappush(left,-move)
                    sumright = sumright-move
                    sumleft = sumleft+move
            mid = -left[0]
        else:#表示
            ans = (len(left)-len(right))*mid-sumleft+sumright + b
            print(mid,ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = []
b = 0

for i in range(n):
	d = [int(i) for i in input().split()]
	if d[0] == 1:
		a.append(d[1])
		b += d[2]
	elif d[0] == 2:
		l = len(a)
		a.sort()
		if l % 2 == 0:
			x = a[int(l/2) - 1]
		else:
			x = a[int((l-1)/2)]
		s = 0
		for _ in a:
			s += abs(x - _)
		print(x, s + b)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())

count = 0
A = []
b = 0
dic = dict()

for q in [[int(i) for i in input().strip().split(' ')] for _ in range(N)]:
  if len(q) == 1:
    median = (count - 1) // 2

    pos = 0
    for x, n in sorted(dic.items()):
      #print('x = {}, n = {}, median = {}'.format(x, n, median))
      pos += n
      if pos > median:
        break

    s = 0
    for a, n in dic.items():
      s += abs(x - a) * n

    print('{} {}'.format(x, s + b))

    # print(q)
  else:
    count = count + 1
    a = q[1]
    if a in dic:
      dic[a] += 1
    else:
      dic[a] = 1

    b += q[2]

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())

A = []
b = 0

for q in [[int(i) for i in input().strip().split(' ')] for _ in range(N)]:
  if len(q) == 1:
    A = sorted(A)
    i = (len(A) - 1) // 2
    # print('i == ', i)
    # print(A)
    x = A[i]
    s = sum([abs(x - v) for v in A]) + b
    #while True:
    #  tmp = sum([abs(x - 1 - v) for v in A])
    #  if tmp != s:
    #    break
    #  x = x - 1

    print('{} {}'.format(x, s))
    # print(q)
  else:
    A.append(q[1])
    b += q[2]

Submission status: Time Limit Exceeded

Solution code:
def process(A: [], b: int):
  last = None

  for x in range(min(A), max(A) + 1):
    s = sum([abs(x - v) for v in A]) + b
    if last is not None and s >= last[1]:
      break
    last = (x, s)

  return last


N = int(input().strip())

Q = []
for _ in range(N):
  Q.append([int(i) for i in input().strip().split(' ')])

A = []
b = 0
for q in Q:
  if len(q) == 1:
    t = process(A, b)
    print('{} {}'.format(t[0], t[1]))
    # print(q)
  else:
    A.append(q[1])
    b += q[2]

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
l = []
r = []
Q = int(input())
ans = 0
l_s = 0
r_s = 0
_,m,b = map(int,input().split())
ans += b
n = 0
for i in range(1,Q):
    s = input()
    if s != '2':
        _,a,b = map(int,s.split())
        ans += b
        if n == 0:
            c,d = sorted([m,a])
            heappush(l,-c)
            heappush(r,d)
            l_s += c
            r_s += d
            m1 = c
        else:
            c,d = heappop(l),heappop(r)
            l_s += c
            r_s -= d
            c = -c
            if n%2 == 1:
                c,m,d = sorted([a,c,d])
                heappush(l,-c)
                heappush(r,d)
                l_s += c
                r_s += d
            else:
                c,m1,m2,d = sorted([m,a,c,d])
                heappush(l,-c)
                heappush(l,-m1)
                heappush(r,d)
                heappush(r,m2)
                l_s += c
                r_s += d
                l_s += m1
                r_s += m2
        n += 1
    else:
        if n == 0:
            print('{} {}'.format(m,ans))
        elif n == 1:
            print('{} {}'.format(m1,r_s-l_s+ans))
        elif n%2 == 0:
            print('{} {}'.format(m,r_s-l_s+ans))
        else:
            print('{} {}'.format(m1,r_s-l_s+ans))

Submission status: Time Limit Exceeded

Solution code:
def qsort(li):
    if len(li) < 2:
        return li
    pivot = li[0]
    li_rest =  li[1:]
    smaller = [x for x in li_rest if x < pivot]
    larger = [x for x in li_rest if x >= pivot]
    return  qsort(smaller) + [pivot] + qsort(larger)
    
Q=int(input())
A=[]
B=0
j=0
Que0=list(map(int,input().split(" ")))
A=[Que0[1]]
B=Que0[2]
min=0
for i in range (1,Q):
    Query=list(map(int,input().split(" ")))
    l=len(A)
    if Query[0]==1:
        if l%2==0 :
            if Query[1]<A[int(l/2)-1]:
                min=min+A[int(l/2)-1]-Query[1]
            elif Query[1]>A[int(l/2)]:
                min=min+Query[1]-A[int(l/2)]
        else:
            min=min+int(abs(A[int((l-1)/2)]-Query[1]))
            
        j=0
        A.append(Query[1])
        A=qsort(A)
        B=B+Query[2]
    else:
        s=int((l-1)/2)
        x=int(A[s])
        print(x,end=" ")
        print(int(min+B))

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
A=[]
B=0
j=0
Que0=list(map(int,input().split(" ")))
A=[Que0[1]]
B=Que0[2]
min=0
for i in range (1,Q):
    Query=list(map(int,input().split(" ")))
    l=len(A)
    if Query[0]==1:
        if l%2==0 :
            if Query[1]<A[int(l/2)-1]:
                min=min+A[int(l/2)-1]-Query[1]
            elif Query[1]>A[int(l/2)]:
                min=min+Query[1]-A[int(l/2)]
        else:
            min=min+int(abs(A[int((l-1)/2)]-Query[1]))
            
        j=0
        while Query[1]>A[j]:
            j=j+1
            if j>=l:
                break
        A.insert(j,Query[1])
        B=B+Query[2]
    else:
        s=int((l-1)/2)
        x=int(A[s])
        print(x,end=" ")
        print(int(min+B))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
Q=int(input())
def func(x,a,b):
    return abs(x-a)+b
A=[]
B=[]
j=0
for i in range (0,Q):
    Query=list(map(int,input().split(" ")))
    if Query[0]==1:
        A=np.append(A,Query[1])
        B=np.append(B,Query[2])
        A=np.sort(A)
        j=j+1
    else:
        s=int((len(A)-1)/2)
        x=int(A[s])
        min=0
        for k in range(0,j):
            min=min+func(x,A[k],B[k])
        print(x,end=" ")
        print(int(min))

Submission status: Time Limit Exceeded

Solution code:
import heapq
Q = int(input())
Query = [[int(_) for _ in input().split()] for _ in range(Q)]
H1 = []
H2 = []
a = b = 0
for query in Query:
    if query[0] == 1:
        m0 = query[1]
        if len(H1) == len(H2):
            if len(H2):
                m1 = heapq.heappop(H2)
                m0, m1 = sorted([m0, m1])
                heapq.heappush(H1, -m0)
                heapq.heappush(H2, m1)
            else:
                heapq.heappush(H1, -m0)
        else:
            m1 = -heapq.heappop(H1)
            m0, m1 = sorted([m0, m1])
            heapq.heappush(H1, -m0)
            heapq.heappush(H2, m1)
        b += query[2]
    else:
        x = -H1[0]
        print(x, x * len(H1) + sum(H1) + sum(H2) - x * len(H2) + b)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
A = []
B = 0
for i in range(Q):
    minX = 0
    inputs = input()
    if inputs == '2':
        if len(A) == 0:
            x = 0
        elif len(A) % 2 == 1:
            x = A[(len(A)-1)//2]
        else:
            x = A[(len(A)-2)//2]
        for smalla in A:
            minX += abs(x - smalla)
        minX += B
        print(x,minX)
    else:
        q,a,b = map(int,inputs.split())
        A.append(a)
        A = sorted(A)
        B += b

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
L,R=[],[]
n=int(input())
B=0
cnt=0
for i in range(n):
    I=input()
    if I[0]=="1":
        a,b,c=map(int,I.split())
        B+=c
        cnt+=1
        if cnt%2:
            x=heappushpop(R,b)
            heappush(L,-x)
        else:
            x=heappushpop(L,-b)
            heappush(R,-x)
    else:
        med=-L[0]
#        print(L,R)
        print(med,med*(len(L)-len(R))+sum(L)+sum(R)+B)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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())
    n, a, b = map(int, line_input())
    left, right = [], []
    left.append(a)
    right.append(a)
    minans =  b
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            if left[-1] <= a <= right[0]:
                left.append(a)
                right.insert(0, a)
            elif a < left[-1]:
                minans += left[-1] - a
                insertpos = bisect_left(left, a)
                left.insert(insertpos, a)
                left.insert(insertpos, a)
                right.insert(0, left.pop())
            else:
                minans += a - right[0]
                insertpos = bisect_left(right, a)
                right.insert(insertpos, a)
                right.insert(insertpos, a)
                left.append(right.pop(0))
        else: print(left[-1], minans)
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush, heappushpop

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

heappush(L, -q[0][1])

for i in range(1, n):
    #print([L, R])
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            p = heappushpop(L, - temp[1])
            heappush(R, - p)
        else:
            p = heappushpop(R, temp[1])
            heappush(L, - p)
        b += temp[2]
    else:
        m = - L[0]
        ans = b
        for x in L:
            ans += abs(m + x)
        for x in R:
            ans += abs(m - x)
        print(m, ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush, heappushpop

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

heappush(L, -q[0][1])

for i in range(1, n):
    #print([L, R])
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            p = heappushpop(L, - temp[1])
            heappush(R, - p)
        else:
            p = heappushpop(R, temp[1])
            heappush(L, - p)
        b += temp[2]
    else:
        m = heappop(L)
        heappush(L, m)
        m *= -1
        ans = b
        for x in L:
            ans += abs(m + x)
        for x in R:
            ans += abs(m - x)
        print(m, ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

heappush(L, -q[0][1])

for i in range(1, n):
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            tl = - heappop(L)
            if temp[1] >= tl:
                heappush(R, temp[1])
                heappush(L, - tl)
            else:
                heappush(L, - temp[1])
                heappush(R, tl)
        else:
            tr = heappop(R)
            if temp[1] <= tr:
                heappush(L, - temp[1])
                heappush(R, tr)
            else:
                heappush(L, - tr)
                heappush(R, temp[1])
        b += temp[2]
    else:
        m = heappop(L)
        heappush(L, m)
        m *= -1
        ans = b
        for x in L:
            ans += abs(m + x)
        for x in R:
            ans += abs(m - x)
        print(m, ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = []
b = 0

for temp in q:
    if temp[0] == 1:
        a.insert(bisect_left(a, temp[1]), temp[1])
        b += temp[2]
    else:
        #print(a)
        m = a[len(a) // 2 + len(a) % 2 - 1]
        ans = b
        for x in a:
            ans += abs(m - x)
        print(m, ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bis
Q = int(input())
minval = 0
argminval = -(10**9)
L, R = [-(10**9)], [10**9]
lenL, lenR = 0, 0

def listupdate(items, new):
    ind = bis.bisect_left(items, new)
    ret = items[:ind]+[new]+items[ind:]
    return ret

for _ in range(Q):
    qi = list(map(int, input().split()))
    if qi[0] == 1:
        ai, bi = qi[1], qi[2]
        LC, RC = L[-1], R[0]
        if lenL == lenR:
            if ai < RC:
                L = listupdate(L, ai)
            else:
                L = listupdate(L, RC)
                R = listupdate(R[1:], ai)
            lenL += 1
            argminval = L[-1]
            minval += abs(argminval - ai) + bi
        else:
            if ai < LC:
                L = listupdate(L[:-1], ai)
                R = listupdate(R, LC)
            else:
                R = listupdate(R, ai)
            lenR += 1
            minval += abs(argminval - ai) + bi
            argminval = L[-1]
    else:
        print("{} {}".format(argminval, minval))

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left

Q = int(input())
Query = [input() for _ in range(Q)]

ans = 0
x = []
c = 0
n = 0

l, r = -float('inf'), float('inf')

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        insort_left(x, a)
        c += b
        n += 1

        if a < l :
            ans += l - a
        elif r < a :
            ans += a - r
            
        l, r = x[(n - 1) // 2], x[n // 2]

    else :
        print(l, ans + c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import heapq

INF = 10 ** 10

Q, = map(int, sys.stdin.readline().rstrip().split(" "))
b_all = 0
sum_value = 0
k_value = 0
tree = None
qs = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(Q)]
# for _ in range(Q):
#     query = list(map(int, sys.stdin.readline().rstrip().split(" ")))

left = []
right = []
a_s = []
current_median = None
heapq.heappush(left, INF)
heapq.heappush(right, INF)
for query in qs:
    if query[0] == 1:
        _, a, b = query
        a_s.append(a)
        b_all += b

        heapq.heappush(left, -a)
        heapq.heappush(right, a)
        heapq.heappush(left, -heapq.heappop(right))
        heapq.heappush(right, -heapq.heappop(left))
        current_median = -left[0]
    else:
        value = 0
        for a in a_s:
            value += abs(a - current_median)
        print(current_median, value+b_all)

exit(0)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

# from matplotlib import pyplot as plt

sys.setrecursionlimit(10000)
INF = float('inf')

Q = int(input())

# def plot(fn):
#     x = np.arange(-10, 10, 1)
#     y = np.array([fn(xa) for xa in x])
#     plt.plot(x, y)
#     plt.grid()
#     plt.show()
#
#
# def g(fn, a, b):
#     return lambda x: fn(x) + abs(x - a) + b
#
#
# f = lambda x: 0
# i = 0
# for _ in range(Q):
#     q = list(map(int, input().split()))
#     if q[0] == 1:
#         a, b = q[1], q[2]
#         f = g(f, a, b)
#     else:
#         plot(f)


# a をソートしたときに真ん中に来る値 x が最小値を持つ
# 中央値しか必要ないのでヒープ 2 つ作って管理
# 中央値より小さいやつ
smalls = []
# 中央値より大きいやつ
larges = []
# こたえ f(x) の最小値
fmin = 0
prev_x = None
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        a, b = q[1], q[2]

        # 適切な方に入れる
        if not larges or a > larges[0]:
            heapq.heappush(larges, a)
        else:
            heapq.heappush(smalls, -a)
        # 偏り解消
        if len(larges) > len(smalls) + 1:
            heapq.heappush(smalls, -heapq.heappop(larges))
        elif len(smalls) > len(larges) + 1:
            heapq.heappush(larges, -heapq.heappop(smalls))

        # x は a の中央値
        if len(smalls) >= len(larges):
            x = -smalls[0]
        else:
            x = larges[0]

        fmin += abs(x - a) + b
        if x != prev_x:
            if prev_x is not None and len(smalls) == len(larges):
                fmin += abs(x - prev_x)
            prev_x = x
    else:
        if len(smalls) >= len(larges):
            x = -smalls[0]
        else:
            x = larges[0]
        print(x, fmin)

Submission status: Time Limit Exceeded

Solution code:

Q = int(input())
query = ['' for i in range(Q)]
for i in range(Q):
    query[i] = input()
#print(query)
minx = 0
minfx = 0
Alist = []
allb = 0
for i in range(Q):
    if query[i] == '2' :
        print(minx, minfx)
    else:
        k, a, b = query[i].split()
        Alist.append(int(a))
        Alist.sort()
        allb += int(b)
        mid = (len(Alist)-1)//2
        minx = Alist[mid]
        minfx = allb + minx * mid -sum(Alist[:mid]) + sum(Alist[mid:]) - minx * len(Alist[mid:])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
query = ['' for i in range(Q)]
for i in range(Q):
    query[i] = input()
#print(query)
minx = 0
minfx = 0
Alist = []
allb = 0
for i in range(Q):
    if query[i] == '2' :
        print(minx, minfx)
    else:
        k, a, b = query[i].split()
        Alist.append(int(a))
        Alist.sort()
        allb += int(b)
        minx = Alist[(len(Alist)-1)//2]
        minfx = allb
        for j in range(len(Alist)):
            minfx += abs(Alist[j] - minx)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
Query = [input() for _ in range(Q)]

x = []
c = 0

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        x.append(a)
        c += b

    else :
        x.sort()

        min_v = float('inf')

        mid_l, mid_r = (len(x) - 1) // 2, len(x) // 2

        for mid in range(mid_l, mid_r + 1) :
            tmp = 0
            xmid = x[mid]

            for xi in x :
                tmp += abs(xi - xmid)
            
            if tmp < min_v :
                min_v = tmp
                min_k = x[mid]
        
        print(min_k, min_v + c)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left

Q = int(input())
Query = [input() for _ in range(Q)]

x = []
c = 0
i = 0

for q in Query :

    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        insort_left(x, a)
        c += b
        i += 1

    else :
        min_v = float('inf')

        mid_l, mid_r = (i - 1) // 2, i // 2
        for mid in range(mid_l, mid_r + 1) :
            tmp = 0
            xmid = x[mid]

            for xi in x :
                tmp += abs(xi - xmid)
            
            if tmp < min_v :
                min_v = tmp
                min_k = x[mid]
        
        print(min_k, min_v + c)