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: Wrong Answer

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

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

        last_left, last_right = -left[0], right[0]
        heapq.heappush(left, -a)
        heapq.heappush(right, a)
        heapq.heappush(left, -heapq.heappop(right))
        heapq.heappush(right, -heapq.heappop(left))
        current_median = -left[0]
        if last_left <= current_median and current_median <= last_right:
            pass
        else:
            a_current += min(abs(last_right - current_median), abs(last_left - current_median))
    else:
        print(current_median, a_current+b_all)

exit(0)

Submission status: Wrong Answer

Solution code:
from bisect import insort_left

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

ans = 0

# 最初の更新クエリを見つけるまで
for k, v in enumerate(Query) :
    if v[0] == '1' :
        a, b = map(int, v[2:].split())
        
        prev, current = 0, a
        x = [a]
        c = b
        break

    else :
        print(0, 0)

i = 1
for q in Query[k+1:] :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        insort_left(x, a)
        c += b
        i += 1
        
        prev, current = current, x[(i - 1) // 2]

        ans += abs(prev - current) + abs(a - current)

    else :
        print(current, ans + c)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 25 22:55:33 2019

@author: Yamazaki Kenichi
"""
import heapq

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

ans = []
Al,Ar = [-(-(10**9+1))],[10**9+1]
B = 0
flg = False
for q in Q2:
    if q[0] == '1':
#        input
        d, a, b = map(int,q.split())
        if not flg:
            heapq.heappush(Al,-a)
            B += b
            flg = True
            continue

        if len(Al) == len(Ar):
            if a < Ar[0]:
                heapq.heappush(Al,-a)
                C = abs(a - (-Al[0]))
#            elif a < Ar[0]:
#                heapq.heappush(Al,-(heapq.heappop(Ar)))
#                heapq.heappush(Ar,a)
#                C = abs(a - (-Al[0]))
            else:
                heapq.heappush(Al,-(heapq.heappop(Ar)))
                heapq.heappush(Ar,a)
                C = abs(a - (-Al[0]))
        else:
            if a < Ar[0]:
                heapq.heappush(Ar,-(heapq.heappop(Al)))
                heapq.heappush(Al,-a)
                C = abs(a - (Ar[0]))
#            elif a < A[]
            else:
                heapq.heappush(Ar,a)
                C = abs(a - (-Al[0]))
        B += (b + C)
#        print(Al,Ar,a,B,b)
    else:
#        output
        ans.append([(-Al[0]),B])
        
for c in ans:
    print(' '.join(map(str,c)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heappushpop
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:
            if len(L) == 0:
                L.append(-q[1])
            else:
                R.append(q[1])
                if -L[0] > R[0]:
                    L[0], R[0] = -R[0], -L[0]
                M = R[0] + L[0]
            continue

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush 
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]))
        heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -R[0], -L[0]
        heappush(R, q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -R[0], -L[0]
    else:
        print(-L[0], B+M)

Submission status: Wrong Answer

Solution code:
from heapq import heappush 
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]))
        heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -R[0], -L[0]
        heappush(R, q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -R[0], -L[0]
    else:
        print(-L[0], B+M)

Submission status: Wrong Answer

Solution code:
from heapq import heappush 
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]))
        heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -L[0], -R[0]
        heappush(R, q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -L[0], -R[0]
    else:
        print(-L[0], B+M)

Submission status: Wrong Answer

Solution code:
from heapq import heappush 
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:
            if len(L) == 0:
                L.append(-q[1])
            else:
                R.append(q[1])
                if -L[0] > R[0]:
                    L[0], R[0] = -R[0], -L[0]
                M = R[0] + L[0]
            continue

        if len(L) > len(R):
            M += abs(q[1] + L[0])
            heappush(R, q[1])
        else:
            M += min(abs(q[1] + L[0]), abs(q[1] - R[0]))
            heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -R[0], -L[0]
    else:
        print(-L[0], B+M)

Submission status: Wrong Answer

Solution code:
from heapq import heappush 
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:
            if len(L) == 0:
                L.append(-q[1])
            else:
                R.append(q[1])
                if -L[0] > R[0]:
                    L[0], R[0] = -R[0], -L[0]
                M = R[0] + L[0]
            continue

        if len(L) > len(R):
            M += abs(q[1] + L[0])
            heappush(R, q[1])
        else:
            M += min(q[1] + L[0], q[1] - R[0])
            heappush(L, -q[1])
        if -L[0] > R[0]:
            L[0], R[0] = -R[0], -L[0]
    else:
        print(-L[0], B+M)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-q1))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,q1))
        
        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

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

Submission status: Wrong Answer

Solution code:
import heapq

Q = int(input())
b_sum = 0
a_list = []
left = []
right = []
res = 0

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        b_sum += query[2]
        if len(left) == 0:
            a = query[1]
            heapq.heappush(left, -a)
        else:
            res += abs(query[1] + left[0])
            if query[1] <= -left[0]:
                heapq.heappush(left, -query[1])
            else:
                heapq.heappush(right, query[1])
        if len(left) < len(right):
            x = heapq.heappop(right)
            y = -left[0]
            res += abs(y - x)
            heapq.heappush(left, -x)
        elif len(left) > len(right) + 1:
            x = - heapq.heappop(left)
            if len(right) != 0:
                y = right[0]
            else:
                y = 0
            heapq.heappush(right, x)
    else:
        print(-left[0], res + b_sum)

Submission status: Wrong Answer

Solution code:
import heapq

Q = int(input())
b_sum = 0
a_list = []
left = []
right = []
res = 0

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        b_sum += query[2]
        if len(left) == 0:
            a = query[1]
            heapq.heappush(left, -a)
        else:
            res += abs(query[1] + left[0])
            if query[1] <= -left[0]:
                heapq.heappush(left, -query[1])
            else:
                heapq.heappush(right, query[1])
        if len(left) < len(right):
            x = heapq.heappop(right)
            y = -left[0]
            res += abs(y - x)
            heapq.heappush(left, -x)
        elif len(left) > len(right) + 1:
            x = - heapq.heappop(left)
            heapq.heappush(right, x)
    else:
        print(-left[0], res + b_sum)

Submission status: Wrong Answer

Solution code:
import heapq

Q = int(input())
b_sum = 0
a_list = []
left = []
right = []
res = 0

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        b_sum += query[2]
        if len(right) == 0:
            a = query[1]
            heapq.heappush(right, -a)
        else:
            res += abs(query[1] + right[0])
            if query[1] <= -right[0]:
                heapq.heappush(right, -query[1])
            else:
                heapq.heappush(left, query[1])
        if len(right) < len(left):
            x = heapq.heappop(left)
            y = -right[0]
            res += abs(y - x)
            heapq.heappush(right, -x)
        elif len(right) > len(left) + 1:
            x = - heapq.heappop(right)
            heapq.heappush(left, x)
    else:
        print(-right[0], res + b_sum)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
j=1
tmp=que[1]
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        q1=que[1]
        b+=que[2]
        tmp=-l[0]
        if j%2==0:
            if q1<=-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<=-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-q1))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,q1))
        
        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

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

Submission status: Wrong Answer

Solution code:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
min=0
j=1
tmp=que[1]
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        q1=que[1]
        b+=que[2]
        tmp=-l[0]
        if j%2==0:
            if q1<=-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<=-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-q1))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,q1))
        
        if -l[0]!=r[0]: min+=abs(tmp-q1)
        else: min+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

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

Submission status: Wrong Answer

Solution code:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
min=0
j=1
tmp=que[1]
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        q1=que[1]
        b+=que[2]
        tmp=-l[0]
        if j%2==0:
            if q1<=-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(l,q1)

        else:
            if q1<=-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-q1))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,q1))
        
        if -l[0]!=r[0]: min+=abs(tmp-q1)
        else: min+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

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

Submission status: Wrong Answer

Solution code:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
l,r=[-que[1]],[que[1]]
min=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]
        tmp=-l[0]
        if j%2==0:
            if que[1]<=-l[0]:
                heapq.heappushpop(l,-que[1])
            else:
                heapq.heappushpop(l,que[1])

        else:
            if que[1]<=-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-que[1]))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,que[1]))
        
        if -l[0]!=r[0]: min+=abs(tmp-que[1])
        else: min+=abs(tmp-que[1])-abs(-l[0]-tmp)
        tmp=-l[0]

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

Submission status: Wrong Answer

Solution code:
import bisect
import heapq

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
l,r=[-que[1]],[que[1]]
min=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]
        tmp=-l[0]
        if j%2==0:
            if que[1]<=-l[0]:
                heapq.heappushpop(l,-que[1])
            else:
                heapq.heappushpop(l,que[1])

        else:
            if que[1]<=-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-que[1]))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,que[1]))
        
        if -l[0]!=r[0]: min+=abs(tmp-que[1])
        else: min+=abs(tmp-que[1])-abs(l[0]-tmp)
        tmp=-l[0]

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

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

# bit = Bit(10)
# bit.add(1, 1)
# bit.add(1, 1)

# # bit.add(2, 2)
# # bit.add(3, 3)
# print(bit.sum(1))

N=int(input())
queries = [tuple(map(int, input().split())) for _ in range(N)]

numl = []
for q in queries:
    if q[0] == 1:
        numl.append(q[1])
numl.sort()
val_to_key = {}

for i,v in enumerate(numl):
    if not v in val_to_key:
        val_to_key[v] = i

# print(numl)
# print(val_to_key)

cum_b = 0
cum_a = 0
bit = Bit(200005)
bit2 = Bit(200005)
cnt = 0

def abs_sum(mid):
    loc_sum = bit.sum(1+mid)
    lft_cnt = bit2.sum(1+mid)
    lef_sum = numl[mid]*lft_cnt - loc_sum
    rig_sum = cum_a-loc_sum - numl[mid]*(cnt-lft_cnt)
    return lef_sum + rig_sum

def solve():
    left = 0
    right = len(numl)-1
    mid = (left+right) // 2
    while left < mid:
        diff = abs_sum(mid+1) - abs_sum(mid)
        if diff < 0:
            left = mid
        else:
            right = mid
        mid = (left+right) // 2

    res1, res_val1 = numl[left], abs_sum(left)+cum_b
    if left < len(numl)-1:
        res2, res_val2 = numl[left+1], abs_sum(left+1)+cum_b

    # print("1:{} {} 2:{} {}".format(res1, res_val1, res2, res_val2))
    if res_val2 < res_val1:
        return res2, res_val2
    else:
        return res1, res_val1

for qu in queries:
    if qu[0] ==  1:
        _, a, b = qu
        bit.add(1+val_to_key[a], a)
        bit2.add(1+val_to_key[a], 1)
        cnt += 1
        cum_b += b
        cum_a += a
    else:
        sol, val = solve()
        print("{} {}".format(sol, val))

# cum = 0
# lis = []
# for _ in range(N):
#     qu=list(map(int, input().split()))
#     if qu[0] == 1:
#         lis.append(qu[1])
#         cum += qu[2]
#     else:

Submission status: Wrong Answer

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

# bit = Bit(10)
# bit.add(1, 1)
# bit.add(1, 1)

# # bit.add(2, 2)
# # bit.add(3, 3)
# print(bit.sum(1))

N=int(input())
queries = [tuple(map(int, input().split())) for _ in range(N)]

numl = []
for q in queries:
    if q[0] == 1:
        numl.append(q[1])
numl.sort()
val_to_key = {}

for i,v in enumerate(numl):
    if not v in val_to_key:
        val_to_key[v] = i

# print(numl)
# print(val_to_key)

cum_b = 0
cum_a = 0
bit = Bit(200005)
bit2 = Bit(200005)
cnt = 0

def abs_sum(mid):
    loc_sum = bit.sum(1+mid)
    lft_cnt = bit2.sum(1+mid)
    lef_sum = numl[mid]*lft_cnt - loc_sum
    rig_sum = cum_a-loc_sum - numl[mid]*(cnt-lft_cnt)
    return lef_sum + rig_sum

def solve():
    left = 0
    right = len(numl)-1
    while left < right:
        mid = (left + right) // 2
        diff = abs_sum(mid+1) - abs_sum(mid)
        if diff < 0:
            left = mid + 1
        else:
            right = mid
    return numl[left], abs_sum(left)+cum_b

for qu in queries:
    if qu[0] ==  1:
        _, a, b = qu
        bit.add(1+val_to_key[a], a)
        bit2.add(1+val_to_key[a], 1)
        cnt += 1
        cum_b += b
        cum_a += a
    else:
        sol, val = solve()
        print("{} {}".format(sol, val))

# cum = 0
# lis = []
# for _ in range(N):
#     qu=list(map(int, input().split()))
#     if qu[0] == 1:
#         lis.append(qu[1])
#         cum += qu[2]
#     else:

Submission status: Wrong Answer

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

# bit = Bit(10)
# bit.add(1, 1)
# bit.add(1, 1)

# # bit.add(2, 2)
# # bit.add(3, 3)
# print(bit.sum(1))

N=int(input())
queries = [tuple(map(int, input().split())) for _ in range(N)]

numl = []
for q in queries:
    if q[0] == 1:
        numl.append(q[1])
numl.sort()
val_to_key = {}

for i,v in enumerate(numl):
    if not v in val_to_key:
        val_to_key[v] = i

# print(numl)
# print(val_to_key)

cum_b = 0
cum_a = 0
bit = Bit(200005)
bit2 = Bit(200005)
cnt = 0

def abs_sum(mid):
    loc_sum = bit.sum(mid)
    lft_cnt = bit2.sum(mid)
    lef_sum = numl[mid]*lft_cnt - loc_sum
    rig_sum = cum_a-loc_sum - numl[mid]*(cnt-lft_cnt)
    return lef_sum + rig_sum

def solve():
    left = 0
    right = len(numl)-1
    while left < right:
        mid = (left + right) // 2
        diff = abs_sum(mid+1) - abs_sum(mid)
        if diff < 0:
            left = mid + 1
        else:
            right = mid
    return numl[left], abs_sum(left)+cum_b

for qu in queries:
    if qu[0] ==  1:
        _, a, b = qu
        bit.add(val_to_key[a], a)
        bit2.add(val_to_key[a], 1)
        cnt += 1
        cum_b += b
        cum_a += a
    else:
        sol, val = solve()
        print("{} {}".format(sol, val))

# cum = 0
# lis = []
# for _ in range(N):
#     qu=list(map(int, input().split()))
#     if qu[0] == 1:
#         lis.append(qu[1])
#         cum += qu[2]
#     else:

Submission status: Wrong Answer

Solution code:
from heapq import*
n=int(input())
x=[]
y=[]
z=0
for i in range(n):
    I=input()
    if I[0]==str(1):
        a,b,c=map(int,I.split())
        z+=c
        if len(x)==len(y):
            heappush(y,b)
            heappush(x,heappop(y))
        else:
            heappush(x,b)
            heappush(y,x.pop())
    
    else:
#        print(x,y)
        tmp=x[-1]
        print(tmp,len(x)*tmp-sum(x or [0])+sum(y or [0])-len(y)*tmp+z)

Submission status: Wrong Answer

Solution code:
import heapq
Q = int( input())
t = 0
q = []
c = 0
s = 0
for _ in range(Q):
    A = list( map( int, input().split()))
    if A[0] == 2:
        if s == t:
            print(a,b)
        m = heapq.nsmallest((t+1)//2, q)[-1]
        a, b = m, sum( list(map( abs, map( lambda x: abs(x-m), q))))+c
        print(a,b)
        s = t
    else:
        c += A[2]
        t += 1
        heapq.heappush(q, A[1])

Submission status: Wrong Answer

Solution code:
import heapq
Q = int( input())
t = 0
q = []
c = 0
s = 0
for _ in range(Q):
    A = list( map( int, input().split()))
    if A[0] == 2:
        if s == t:
            print(a,b)
        m = heapq.nsmallest(t//2+1, q)[-1]
        a, b = m, sum( list(map( abs, map( lambda x: abs(x-m), q))))+c
        print(a,b)
        s = t
    else:
        c += A[2]
        t += 1
        heapq.heappush(q, A[1])

Submission status: Wrong Answer

Solution code:
import heapq
Q = int( input())
t = 0
q = []
c = 0
s = 0
for _ in range(Q):
    A = list( map( int, input().split()))
    if A[0] == 2:
        m = heapq.nsmallest(t//2+1, q)[-1]
        print(m, sum( list(map( abs, map( lambda x: abs(x-m), q))))+c)
    else:
        c += A[2]
        t += 1
        heapq.heappush(q, A[1])

Submission status: Wrong Answer

Solution code:
import heapq
Q = int( input())
t = 0
q = []
c = 0
for _ in range(Q):
    A = list( map( int, input().split()))
    if A[0] == 2:
        m = heapq.nsmallest(t//2+1, q)[-1]
        print(m, sum( list(map( abs, map( lambda x: abs(x-m), q))))+c)
    else:
        c += A[2]
        t += 1
        heapq.heappush(q, A[1])

Submission status: Wrong Answer

Solution code:
import heapq
Q = int( input())
t = 0
q = []
c = 0
for _ in range(Q):
    A = list( map( int, input().split()))
    if A[0] == 2:
        m = heapq.nsmallest(t//2+1, q)[-1]
        print(m, sum( list(map( abs, map( lambda x: abs(x-m), q))))+c)
    else:
        c += A[2]
        heapq.heappush(q, A[1])

Submission status: Wrong Answer

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

import heapq

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


A_left_sum = 0
A_left = []
A_right_sum = 0
A_right = []
A_med = None
query_size = 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]
      if A_med is None:
        A_med = a
      else:
        if query_size%2 == 0: # even
          left_max = -A_left[0]
          right_min = A_right[0]
          if a < left_max:
            heapq.heappushpop(A_left, a)
            A_left_sum += a - left_max
            A_med = left_max
          elif a > right_min:
            heapq.heappushpop(A_right, a)
            A_right_sum += a - right_min
            A_med = right_min
          else:
            A_med = a
        else: # odd
          if A_med <= a:
            heapq.heappush(A_left, -A_med)
            heapq.heappush(A_right, a)
            A_left_sum += A_med
            A_right_sum += a
          else:
            heapq.heappush(A_left, -a)
            heapq.heappush(A_right, A_med)
            A_right_sum += A_med
            A_left_sum += a

      # print(As)
      # print(A_left)
      # print(A_right)
      query_size += 1

      b_sum += query[2]
    else:
      if query_size%2 == 0: #even
        print(-A_left[0], A_right_sum - A_left_sum + b_sum)
      else:
        print(A_med, A_right_sum - A_left_sum + b_sum)

Submission status: Wrong Answer

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

import heapq

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


A_left_sum = 0
A_left = []
A_right_sum = 0
A_right = []
A_med = None
query_size = 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]
      if A_med is None:
        A_med = a
      else:
        if query_size%2 == 0: # even
          left_max = -A_left[0]
          right_min = A_right[0]
          if a < left_max:
            heapq.heappushpop(A_left, a)
            heapq.heappush(A_left, a)
            A_left_sum += a - left_max
            A_med = left_max
          elif a > right_min:
            heapq.heappushpop(A_right, a)
            A_right_sum += a - right_min
            A_med = right_min
          else:
            A_med = a
        else: # odd
          if A_med <= a:
            heapq.heappush(A_left, -A_med)
            heapq.heappush(A_right, a)
            A_left_sum += A_med
            A_right_sum += a
          else:
            heapq.heappush(A_left, -a)
            heapq.heappush(A_right, A_med)
            A_right_sum += A_med
            A_left_sum += a

      # print(As)
      # print(A_left)
      # print(A_right)
      query_size += 1

      b_sum += query[2]
    else:
      if query_size%2 == 0: #even
        print(-A_left[0], A_right_sum - A_left_sum + b_sum)
      else:
        print(A_med, A_right_sum - A_left_sum + b_sum)

Submission status: Wrong Answer

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

import heapq

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


A_left_sum = 0
A_left = []
A_right_sum = 0
A_right = []
A_med = None
query_size = 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]
      if A_med is None:
        A_med = a
      else:
        if query_size%2 == 0: # even
          left_max = -A_left[0]
          right_min = A_right[0]
          if a < left_max:
            heapq.heappop(A_left)
            A_left_sum += a - left_max
            A_med = left_max
          elif a > right_min:
            heapq.heappop(A_right)
            A_right_sum += a - right_min
            A_med = right_min
          else:
            A_med = a
        else: # odd
          if A_med <= a:
            heapq.heappush(A_left, -A_med)
            heapq.heappush(A_right, a)
            A_left_sum += A_med
            A_right_sum += a
          else:
            heapq.heappush(A_left, -a)
            heapq.heappush(A_right, A_med)
            A_right_sum += A_med
            A_left_sum += a

      # print(As)
      # print(A_left)
      # print(A_right)
      query_size += 1

      b_sum += query[2]
    else:
      if query_size%2 == 0: #even
        print(-A_left[0], A_right_sum - A_left_sum + b_sum)
      else:
        print(A_med, A_right_sum - A_left_sum + b_sum)