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:
from heapq import heappush, heappop
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(L, -q[1])
            heappush(R, -heappop(L))
        else:
            heappush(R, q[1])
            heappush(R, q[1])
            heappush(L, -heappop(R))
    else:
        print(-L[0], B+M)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush,heappop

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return tuple(map(int, ss_raw()))

INF = 1<<29

class MedianHeap:
    def __init__(self):
        self.lupper = []
        self.rlower =[]
        self.s=0
    def push(self,a):
        L = self.lupper
        R = self.rlower
        if len(L)== 0 or a<=-L[0]:
            heappush(L,-a)
            self.s+=-L[0]-a
            if len(L)-len(R)>=2:
                heappush(R,-heappop(L))
        else:
            heappush(R,a)
            self.s+=a+L[0]
            if len(R)>len(L):
                self.s+=-L[0]-R[0]
                heappush(L,-heappop(R))

def main():
    Q = int_raw()
    sb = 0
    lupper = []
    rlower = []
    s = 0
    for _ in range(Q):
        cmds = tuple(map(int,input().split()))
        if cmds[0]==1:
            a,b = cmds[1:]
            sb+= b
            if len(lupper)== 0 or a<=-lupper[0]:
                heappush(lupper,-a)
                s+=-lupper[0]-a
                if len(lupper)-len(rlower)>=2:
                    heappush(rlower,-heappop(lupper))
            else:
                heappush(rlower,a)
                s+=a+lupper[0]
                if len(rlower)>len(lupper):
                    s+=-lupper[0]-rlower[0]
                    heappush(lupper,-heappop(rlower))  
        else:
            print (-lupper[0], s+sb)
    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return tuple(map(int, ss_raw()))

INF = 1<<29

class MedianHeap:
    def __init__(self):
        self.lupper = []
        self.rlower =[]
        self.s=0
    def push(self,a):
        L = self.lupper
        R = self.rlower
        if len(L)== 0 or a<=-L[0]:
            heappush(L,-a)
            self.s+=-L[0]-a
            if len(L)-len(R)>=2:
                heappush(R,-heappop(L))
        else:
            heappush(R,a)
            self.s+=a+L[0]
            if len(R)>len(L):
                self.s+=-L[0]-R[0]
                heappush(L,-heappop(R))

        
def main():
    Q = int_raw()
    sb = 0
    mh = MedianHeap()
    for _ in range(Q):
        cmds = tuple(map(int,input().split()))
        if cmds[0]==1:
            a,b = cmds[1:]
            sb+= b
            mh.push(a)
        else:
            print (-mh.lupper[0], mh.s+sb)
    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

DIV = 10**9+7

def mod_inv(a,mod = DIV):
    return pow(a,mod-2,mod)

def ncr(n,r, mod =DIV):
	r = min(r,n-r)
	ret = 1
	for i in range(1,r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * pow(i, mod-2, mod) % mod
	return ret

class MedianHeap:
    def __init__(self):
        self.lupper = []
        self.rlower =[]
        self.s=0
    def push(self,a):
        L = self.lupper
        R = self.rlower
        if len(L)== 0 or a<=-L[0]:
            heappush(L,-a)
            self.s+=-L[0]-a
        else:
            heappush(R,a)
            self.s+=a+L[0]
        if len(R)>len(L):
            self.s+=-L[0]-R[0]
            heappush(L,-heappop(R))
        if len(L)-len(R)>=2:
            heappush(R,-heappop(L))

        
def main():
    Q = int_raw()
    sb = 0
    mh = MedianHeap()
    for _ in range(Q):
        cmds = ints_raw()
        if cmds[0]==1:
            a,b = cmds[1:]
            sb+= b
            mh.push(a)
        else:
            print (-mh.lupper[0], mh.s+sb)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
min=0
l,r=0,0
j=1
tmp=que[1]
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        a.insert(  bisect.bisect_left(a,que[1]), que[1] )
        if j%2==0: r+=1
        else: l+=1
        
        if a[l]!=a[r]: min+=abs(tmp-que[1])
        else: min+=abs(tmp-que[1])-abs(a[l]-tmp)
        tmp=a[l]

    elif que[0]==2:
        print(tmp,min+b)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# from collections import defaultdict
# from functools import reduce

import bisect

# s = input()
Q = int(input())
# A = list(map(int, input().split()))
# n, m, k = map(int, input().split())


As = []
A_left = 0
A_right = 0

b_sum = 0

# n = len(As)
# n is odd:
# A_left + As[n//2] + B_left
# n is even:
# A_left + B_left

for i in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
      a =  query[1]
      n = len(As)
      if n == 0:
        As.append(a)
      else:
        idx = bisect.bisect_left(As, a)
        if n%2 == 0: # even
          if idx < n//2:
            A_left += a
            A_left -= As[n//2-1]
          elif idx > n//2:
            A_right += a
            A_right -= As[n//2]
        else: # odd
          if idx <= n//2:
            A_left += a
            A_right += As[n//2]
          else:
            A_right += a
            A_left += As[n//2]
        bisect.insort_left(As, a)

      # print(As)
      # print(A_left)
      # print(A_right)

      b_sum += query[2]
    else:
      n = len(As)
      if n%2 == 0: #even
        print(As[n//2-1], A_right - A_left + b_sum)
      else:
        print(As[n//2], A_right - A_left + b_sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce

import bisect

# s = input()
Q = int(input())
# A = list(map(int, input().split()))
# n, m, k = map(int, input().split())


As = []
A_left = 0
A_right = 0

b_sum = 0

# n = len(As)
# n is odd:
# A_left + As[n//2] + B_left
# n is even:
# A_left + B_left

for i in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
      a =  query[1]
      n = len(As)
      if n == 0:
        As.append(a)
      else:
        idx = bisect.bisect_left(As, a)
        if n%2 == 0: # even
          if idx < n//2:
            A_left += a
            A_left -= As[n//2-1]
          elif idx > n//2:
            A_right += a
            A_right -= As[n//2]
        else: # odd
          if idx <= n//2:
            A_left += a
            A_right += As[n//2]
          else:
            A_right += a
            A_left += As[n//2]
        bisect.insort_left(As, a)

      # print(As)
      # print(A_left)
      # print(A_right)

      b_sum += query[2]
    else:
      n = len(As)
      if n%2 == 0: #even
        print(As[n//2-1], A_right - A_left + b_sum)
      else:
        print(As[n//2], A_right - A_left + b_sum)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
N = int(input())
s = list(map(int,input().split()))
a, b = s[1], s[2]
L = []
R = []
heappush(L,-a)
heappush(R,a)

bsum = b
t = 0
for k in range(N-1):
    s = input()
    if s[0] == "1":
        s = list(map(int,s.split()))
        a = s[1]
        b = s[2]
        bsum += b
        if -L[0] <= a <= R[0]:
            pass
        else:
            t += min(abs(a+L[0]),abs(a-R[0]))
        heappush(L,-a)
        heappush(R,a)
        if -L[0] > R[0]:
            c = heappop(L)
            d = heappop(R)
            heappush(R,-c)
            heappush(L,-d)
    else:
        print(-L[0], t+bsum)

Submission status: Time Limit Exceeded

Solution code:
import bisect
Q = int(input().rstrip())

bias = 0
vs = []

qi = 0
for _ in range(Q):
    query = list(map(int, input().rstrip().split(" ")))
    if len(query) == 3:
        _, v, b = query
        qi += 1
        bisect.insort_left(vs, v)
        bias += b
        if qi == 1:
            abs_sum = 0
            med = v
            medp = 0
        else:
            if qi % 2 == 0:
                if v <= med:
                    # * ^ + -> v * ^ + -> v ^ + +
                    #       -> * v ^ + -> * ^ + +
                    # medp -> same
                    # med -> new
                    # abs_sum -> += abs(new_med - med) + abs(new_med - v) = (med - new_med) + (new_med - v) = med - v
                    abs_sum += med - v
                    med = vs[medp]
                else:
                    # * ^ + -> * ^ + v
                    #       -> * ^ v +
                    # medp -> same
                    # med -> same
                    # abs_sum -> += abs(med - v) = v - med
                    abs_sum += v - med
            else:
                if v <= med:
                    # * ^ + + -> v * ^ + +
                    #         -> * v ^ + +
                    # ^ + -> v ^ +
                    # medp -> += 1
                    # med -> same
                    # abs_sum -> += abs(med - v) = med - v
                    abs_sum += med - v
                    medp += 1
                else:
                    # * ^ + + -> * ^ + + v -> * * ^ + v
                    #         -> * ^ v + + -> * * ^ + +
                    # medp -> += 1
                    # med -> new
                    # abs_sum -> += abs(new_med - v) = v - new_med
                    medp += 1
                    med = vs[medp]
                    abs_sum += v - med
    else:
        print(med, abs_sum+bias, flush=False)

Submission status: Time Limit Exceeded

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

bias = 0
vs = []

qi = 0
for query in queries:
    if len(query) == 3:
        _, v, b = query
        qi += 1
        bisect.insort_left(vs, v)
        bias += b
        if qi == 1:
            abs_sum = 0
            med = v
            medp = 0
        else:
            if qi % 2 == 0:
                if v <= med:
                    # * ^ + -> v * ^ + -> v ^ + +
                    #       -> * v ^ + -> * ^ + +
                    # medp -> same
                    # med -> new
                    # abs_sum -> += abs(new_med - med) + abs(new_med - v) = (med - new_med) + (new_med - v) = med - v
                    abs_sum += med - v
                    med = vs[medp]
                else:
                    # * ^ + -> * ^ + v
                    #       -> * ^ v +
                    # medp -> same
                    # med -> same
                    # abs_sum -> += abs(med - v) = v - med
                    abs_sum += v - med
            else:
                if v <= med:
                    # * ^ + + -> v * ^ + +
                    #         -> * v ^ + +
                    # ^ + -> v ^ +
                    # medp -> += 1
                    # med -> same
                    # abs_sum -> += abs(med - v) = med - v
                    abs_sum += med - v
                    medp += 1
                else:
                    # * ^ + + -> * ^ + + v -> * * ^ + v
                    #         -> * ^ v + + -> * * ^ + +
                    # medp -> += 1
                    # med -> new
                    # abs_sum -> += abs(new_med - v) = v - new_med
                    medp += 1
                    med = vs[medp]
                    abs_sum += v - med
    else:
        print(med, abs_sum+bias, flush=False)

Submission status: Time Limit Exceeded

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

bias = 0
vs = []

qi = 0
#for query in queries:
#    if len(query) == 3:
#        _, v, b = query
for _ in range(Q):
    query = input()
    if query[0] == "1":
        v, b = map(int, query[2:].split(" "))
        qi += 1
        bisect.insort_left(vs, v)
        bias += b
        if qi == 1:
            abs_sum = 0
            med = v
            medp = 0
        else:
            if qi % 2 == 0:
                if v <= med:
                    # * ^ + -> v * ^ + -> v ^ + +
                    #       -> * v ^ + -> * ^ + +
                    # medp -> same
                    # med -> new
                    # abs_sum -> += abs(new_med - med) + abs(new_med - v) = (med - new_med) + (new_med - v) = med - v
                    abs_sum += med - v
                    med = vs[medp]
                else:
                    # * ^ + -> * ^ + v
                    #       -> * ^ v +
                    # medp -> same
                    # med -> same
                    # abs_sum -> += abs(med - v) = v - med
                    abs_sum += v - med
            else:
                if v <= med:
                    # * ^ + + -> v * ^ + +
                    #         -> * v ^ + +
                    # ^ + -> v ^ +
                    # medp -> += 1
                    # med -> same
                    # abs_sum -> += abs(med - v) = med - v
                    abs_sum += med - v
                    medp += 1
                else:
                    # * ^ + + -> * ^ + + v -> * * ^ + v
                    #         -> * ^ v + + -> * * ^ + +
                    # medp -> += 1
                    # med -> new
                    # abs_sum -> += abs(new_med - v) = v - new_med
                    medp += 1
                    med = vs[medp]
                    abs_sum += v - med
    else:
        print(med, abs_sum+bias)

Submission status: Time Limit Exceeded

Solution code:
def main():
    Q = int(input())
    _, a1, b1 = map(int, input().split())
    As = [a1]
    anow = a1
    ans = b1
    cnt = 0
    for _ in range(Q-1):
        l = list(map(int, input().split()))
        if l == [2]:
            print(anow, ans)
        else:
            _, a, b = l
            up = cnt
            lo = 0
            if a <= As[lo]:
                As = [a] + As
                cnt += 1
            elif a >= As[up]:
                As = As + [a]
                cnt += 1
            else:
                while up-lo > 1:
                    mid = (up+lo)//2
                    if As[mid] <= a:
                        lo = mid
                    else:
                        up = mid
                As = As[:lo+1]+[a]+As[lo+1:]
                cnt += 1
            if cnt % 2 == 1:
                ans += b + abs(anow-a)
                anow = As[cnt//2]
            else:
                m = As[cnt//2]
                if a == m:
                    ans += b
                    anow = m
                else:
                    anow = m
                    ans += abs(a-m)+b
main()

Submission status: Time Limit Exceeded

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

bias = 0
vs = []

qi = 0
for query in queries:
    if len(query) == 3:
        qi += 1
        _, v, b = query
        #bisect.insort_left(vs, v)
        bi = bisect.bisect_left(vs, v)
        vs = vs[:bi] + [v] + vs[bi:]
        bias += b
        if qi == 1:
            abs_sum = 0
            med = v
            medp = 0
        else:
            if qi % 2 == 0:
                if v <= med:
                    # * ^ + -> v * ^ + -> v ^ + +
                    #       -> * v ^ + -> * ^ + +
                    # medp -> same
                    # med -> new
                    # abs_sum -> += abs(new_med - med) + abs(new_med - v) = (med - new_med) + (new_med - v) = med - v
                    abs_sum += med - v
                    med = vs[medp]
                else:
                    # * ^ + -> * ^ + v
                    #       -> * ^ v +
                    # medp -> same
                    # med -> same
                    # abs_sum -> += abs(med - v) = v - med
                    abs_sum += v - med
            else:
                if v <= med:
                    # * ^ + + -> v * ^ + +
                    #         -> * v ^ + +
                    # ^ + -> v ^ +
                    # medp -> += 1
                    # med -> same
                    # abs_sum -> += abs(med - v) = med - v
                    abs_sum += med - v
                    medp += 1
                else:
                    # * ^ + + -> * ^ + + v -> * * ^ + v
                    #         -> * ^ v + + -> * * ^ + +
                    # medp -> += 1
                    # med -> new
                    # abs_sum -> += abs(new_med - v) = v - new_med
                    medp += 1
                    med = vs[medp]
                    abs_sum += v - med
    else:
        print(med, abs_sum+bias)

Submission status: Time Limit Exceeded

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

bias = 0
vs = []

#import time
#s1 = time.time()
#e1 = None
#e2 = None



qi = 0
for query in queries:
    if len(query) == 3:
        qi += 1
        _, v, b = query
        bisect.insort_left(vs, v)
        bias += b
        if qi == 1:
            abs_sum = 0
            med = v
            medp = 0
        else:
            if qi % 2 == 0:
                if v <= med:
                    # * ^ + -> v * ^ + -> v ^ + +
                    #       -> * v ^ + -> * ^ + +
                    # medp -> same
                    # med -> new
                    # abs_sum -> += abs(new_med - med) + abs(new_med - v) = (med - new_med) + (new_med - v) = med - v
                    abs_sum += med - v
                    med = vs[medp]
                else:
                    # * ^ + -> * ^ + v
                    #       -> * ^ v +
                    # medp -> same
                    # med -> same
                    # abs_sum -> += abs(med - v) = v - med
                    abs_sum += v - med
            else:
                if v <= med:
                    # * ^ + + -> v * ^ + +
                    #         -> * v ^ + +
                    # ^ + -> v ^ +
                    # medp -> += 1
                    # med -> same
                    # abs_sum -> += abs(med - v) = med - v
                    abs_sum += med - v
                    medp += 1
                else:
                    # * ^ + + -> * ^ + + v -> * * ^ + v
                    #         -> * ^ v + + -> * * ^ + +
                    # medp -> += 1
                    # med -> new
                    # abs_sum -> += abs(new_med - v) = v - new_med
                    medp += 1
                    med = vs[medp]
                    abs_sum += v - med
    else:
        #if e1 is None:
        #    e1 = time.time()
        #i = (len(vs)+1) // 2 - 1
        #p = vs[i]
        #l = p*i - sum(vs[:i])
        #r = sum(vs[i:]) - (p*(len(vs)-i))
        #s = l + r
        #print(p, s+bias)

        #print(vs, medp, med, abs_sum, bias, file=sys.stderr)
        print(med, abs_sum+bias)

#e2 = time.time()
#print(e1-s1, e2-e1, file=sys.stderr)

Submission status: Time Limit Exceeded

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

Q = int(input())

a = []
a_new = []
b_sum = 0
minima = 0
argmin = 10**10
shift = 0
for i in range(Q):
    ipt = list(map(int, input().split()))
    if len(ipt) == 3:
        a.append(ipt[1])
        argmin_new = statistics.median_low(a)
        if argmin == 10**10:
            argmin = argmin_new
        minima += abs(ipt[1] - argmin_new) + (abs(argmin - argmin_new)) * ((len(a) + 1) % 2)
        b_sum += ipt[2]
        argmin = argmin_new
    else:
        print(argmin, minima + b_sum)

Submission status: Time Limit Exceeded

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

Q = int(input())

a = []
a_new = []
b_sum = 0
minima = 0
argmin = 10**10
shift = 0
for i in range(Q):
    ipt = list(map(int, input().split()))
    if len(ipt) == 3:
        if len(a) == 0:
            a.append(ipt[1])
        else:
            a.insert(bisect.bisect_left(a, ipt[1]), ipt[1])
        argmin_new = a[(len(a) - 1) // 2]
        if argmin == 10**10:
            argmin = argmin_new
        minima += abs(ipt[1] - argmin_new) + (abs(argmin - argmin_new)) * ((len(a) + 1) % 2)
        b_sum += ipt[2]
        argmin = argmin_new
    else:
        print(argmin, minima + b_sum)

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q = int(input())

a = []
a_new = []
b_sum = 0
minima = 0
argmin = 10**10
shift = 0
for i in range(Q):
    ipt = list(map(int, input().split()))
    if len(ipt) == 3:
        if len(a) == 0:
            a.append(ipt[1])
        else:
            a.insert(bisect.bisect_left(a, ipt[1]), ipt[1])
        argmin_new = a[(len(a) - 1) // 2]
        if argmin == 10**10:
            argmin = argmin_new
        minima += abs(ipt[1] - argmin_new) + (abs(argmin - argmin_new)) * ((len(a) + 1) % 2)
        b_sum += ipt[2]
        argmin = argmin_new
    else:
        print(argmin, minima + b_sum)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
_, a1, b1 = map(int, input().split())
As = [a1]
anow = a1
ans = b1
cnt = 0
for _ in range(Q-1):
    l = list(map(int, input().split()))
    if l == [2]:
        print(anow, ans)
    else:
        _, a, b = l
        up = cnt
        lo = 0
        if a <= As[lo]:
            As = [a] + As
            cnt += 1
        elif a >= As[up]:
            As = As + [a]
            cnt += 1
        else:
            while up-lo > 1:
                mid = (up+lo)//2
                if As[mid] <= a:
                    lo = mid
                else:
                    up = mid
            As = As[:lo+1]+[a]+As[lo+1:]
            cnt += 1
        if cnt % 2 == 1:
            ans += b + abs(anow-a)
            anow = As[cnt//2]
        else:
            m = As[cnt//2]
            if a == m:
                ans += b
                anow = m
            else:
                anow = m
                ans += abs(a-m)+b

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
q = int(input())
tei = 0
x = []
nnn = []
for i in range(q):
        nnn.append(input().rstrip())
for i in range(q):
        nn = nnn[i]
        if int(nn[0]) == 1:
                _,a,b = map(int,nn.split())
                x.append(a)
                tei += b
        else:
                x.sort()
                t = x[(len(x)-1)//2]
                ans = 0
                for j in x:
                        ans += abs(t-j)
                print(t,tei+ans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
Y = []
D = []
S = [0] * Q
s = 0
for i in range(Q):
    a = list(map(int, input().split()))
    Y.append(a)
    if a[0] == 1:
        D.append(a[1])
        s += a[2]
    S[i] = s

D = sorted(list(set(D)))
INV = {}
for i in range(len(D)):
    INV[D[i]] = i

N = 17
X = [0] * (2**(N+1)-1)
C = [0] * (2**(N+1)-1)

def add(j, x):
    i = 2**N + j - 1
    while i >= 0:
        X[i] += x
        C[i] += 1
        i = (i-1) // 2

def rangeof(i):
    s = (len(bin(i+1))-3)
    l = ((i+1) - (1<<s)) * (1<<N-s)
    r = l + (1<<N-s)
    return (l, r)

def rangesum(a, b):
    l = a + (1<<N)
    r = b + (1<<N)
    s = 0
    while l < r:
        if l%2:
            s += X[l-1]
            l += 1
        if r%2:
            r -= 1
            s += X[r-1]
        l >>= 1
        r >>= 1
    return s
def rangecnt(a, b):
    l = a + (1<<N)
    r = b + (1<<N)
    s = 0
    while l < r:
        if l%2:
            s += C[l-1]
            l += 1
        if r%2:
            r -= 1
            s += C[r-1]
        l >>= 1
        r >>= 1
    return s

c = 0
su = 0
CC = [0] * (2**N)
for i in range(Q):
    y = Y[i]
    if y[0] == 1:
        add(INV[y[1]], y[1])
        CC[INV[y[1]]] += 1
        c += 1
        su += y[1]
    else:
        l, r = 0, 2**N
        while True:
            m = (l+r)//2
            rc = rangecnt(0, m)
            if rc >= (c+1)//2:
                r = m
            elif rc + CC[m] <= (c-1)//2:
                l = m
            else:
                break
        rs = rangesum(0, m)
        print(D[m], D[m]*rc-rs+(su-rs)-(c-rc)*D[m]+S[i])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
Y = []
D = []
S = [0] * Q
s = 0
for i in range(Q):
    a = list(map(int, input().split()))
    Y.append(a)
    if a[0] == 1:
        D.append(a[1])
        s += a[2]
    S[i] = s

D = sorted(list(set(D)))
INV = {}
for i in range(len(D)):
    INV[D[i]] = i

N = 17
X = [0] * (2**(N+1)-1)
C = [0] * (2**(N+1)-1)

def add(j, x):
    i = 2**N + j - 1
    while i >= 0:
        X[i] += x
        C[i] += 1
        i = (i-1) // 2

def rangeof(i):
    s = (len(bin(i+1))-3)
    l = ((i+1) - (1<<s)) * (1<<N-s)
    r = l + (1<<N-s)
    return (l, r)

def rangesum(a, b, i=0):
    l, r = rangeof(i)
    if l >= b or r <= a:
        return 0
    if a <= l and r <= b:
        return X[i]
    return rangesum(a, b, 2*i+1) + rangesum(a, b, 2*i+2)
def rangecnt(a, b, i=0):
    l, r = rangeof(i)
    if l >= b or r <= a:
        return 0
    if a <= l and r <= b:
        return C[i]
    return rangecnt(a, b, 2*i+1) + rangecnt(a, b, 2*i+2)

def rangesum(a, b):
    l = a + (1<<N)
    r = b + (1<<N)
    s = 0
    while l < r:
        if l%2:
            s += X[l-1]
            l += 1
        if r%2:
            r -= 1
            s += X[r-1]
        l >>= 1
        r >>= 1
    return s

c = 0
su = 0
CC = [0] * (2**N)
for i in range(Q):
    y = Y[i]
    if y[0] == 1:
        add(INV[y[1]], y[1])
        CC[INV[y[1]]] += 1
        c += 1
        su += y[1]
    else:
        l, r = 0, 2**N
        while True:
            m = (l+r)//2
            rc = rangecnt(0, m)
            if rc >= (c+1)//2:
                r = m
            elif rc + CC[m] <= (c-1)//2:
                l = m
            else:
                break
        rs = rangesum(0, m)
        print(D[m], D[m]*rc-rs+(su-rs)-(c-rc)*D[m]+S[i])

Submission status: Time Limit Exceeded

Solution code:
import bisect as bi
Q = int(input())
a_li = []
scalar = 0
length = 0
for i in range(Q):
    query = list(map(int,input().split()))    
    if query[0] == 1:
        bi.insort_left(a_li,query[1])
        scalar += query[2]
        length += 1
#         print(a_li)
    
    if query[0] == 2:
#         print(a_li)
        if length % 2 ==0:
            middle = int(length/2)
            anslin = - sum(a_li[:middle]) + sum(a_li[middle:])
            position = a_li[middle-1]
        else:
            middle = int((length-1)/2) #5 -> 2, 7-> 3
            anslin = - sum(a_li[:middle]) + sum(a_li[middle+1:])
            position = a_li[middle]
        ans = anslin + scalar
        print(position,ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

Q = int(input())

A = []
B = 0
S1, S2 = [], []
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)
        if i>0:
            S1.insert(i, S1[i-1])
        else:
            S1.insert(i, 0)
        for k in range(i,len(S1)):
            S1[k] += a
        j = len(S2)-i
        if j>0:
            S2.insert(j, S2[j-1])
        else:
            S2.insert(j, 0)
        for k in range(j,len(S2)):
            S2[k] += a 
        B += b
    else:
        i = (len(A)-1)//2
        a = A[i]
        s = S2[i]-S1[i]+B
        print(a, s)

Submission status: Time Limit Exceeded

Solution code:
import 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)