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: Accepted

Solution code:
import heapq


class DynamicMedian():
    """値をO(logN)で追加し、中央値クエリにO(1)で応える
    add(val): valを追加する
    median_low(): 小さい方の中央値(low median)を返す
    median_high(): 大きい方の中央値(high median)を返す
    """
    def __init__(self):
        self.left_q = []   # 小さい値を降順で格納する
        self.right_q = []  # 大きい値を昇順で格納する
        self.left_sum = 0
        self.right_sum = 0
        
    def add(self, val):
        """valを追加する"""
        if len(self.left_q) == len(self.right_q):
            self.left_sum += val
            val = -heapq.heappushpop(self.left_q, -val)
            self.left_sum -= val
            heapq.heappush(self.right_q, val)
            self.right_sum += val
        else:
            self.right_sum += val
            val = heapq.heappushpop(self.right_q, val)
            self.right_sum -= val
            heapq.heappush(self.left_q, -val)
            self.left_sum += val
            
    def median_low(self):
        """小さい方のmedianを返す"""
        if len(self.left_q) + 1 == len(self.right_q):
            return self.right_q[0]
        else:
            return -self.left_q[0]

    def median_high(self):
        """大きい方のmedianを返す"""
        return self.right_q[0]

q = int(input())
info = [list(map(int, input().split())) for i in range(q)]
dm = DynamicMedian()

b = 0
for i in range(q):
    if info[i][0] == 1:
        _, tmp_a, tmp_b = info[i]
        dm.add(tmp_a)
        b += tmp_b
    else:
        med = dm.median_high()
        lsum = dm.left_sum
        rsum = dm.right_sum
        lnum = len(dm.left_q)
        rnum = len(dm.right_q)
        tmp = (lnum*med - lsum) + (rsum - rnum*med)
        print(dm.median_low(), tmp + b)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        self.total += w
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index


q = I()
query = []
A = []
for _ in range(q):
    l = LI()
    if l[0] == 1:
        A += [l[1]]
    query += [l]



ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i


bit1 = BIT(len(A))
bit2 = BIT(len(A))
n = 0
B = 0
for l in query:
    if l[0] == 1:
        B += l[2]
        bit1.add(co_to_ind[l[1]], 1)
        bit2.add(co_to_ind[l[1]], l[1])
        n += 1
    else:
        min_ind = bit1.search(n // 2 + bool(n % 2))
        d = n // 2 + bool(n % 2)
        min_val = bit2.interval_sum(min_ind + 1, bit2.size) - bit1.interval_sum(min_ind + 1, bit1.size) * ind_to_co[min_ind] \
            + bit1.sum(min_ind - 1) * ind_to_co[min_ind] - bit2.sum(min_ind - 1) + B
        print(ind_to_co[min_ind], min_val)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    k=int(input())
    score=0
    B=0

    from heapq import heappush,heappop
    q=[] # 小さいほうの最大をとる→マイナスにして入れる
    Q=[] # 大きいほうの最小をとる

    for _ in range(k):
        s=input()
        if(s[0]=='1'):
            s,a,b=map(int,s.split())
            heappush(q,-a)
            heappush(Q,a)
            B+=b
            # 大小関係が逆転しているかを判断する
            t=-q[0]; T=Q[0]
            if(t>T):
                score+=t-T
                heappop(q); heappop(Q)
                heappush(q,-T); heappush(Q,t)
        else:
            print(-q[0],score+B)
resolve()

Submission status: Accepted

Solution code:
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # O(log(N))
    def search(self, c):
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        return ind
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()


import sys
input = sys.stdin.readline

Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

A = []
for i in range(Q):
    if Query[i][0] == 1:
        A.append(Query[i][1])

# 座標圧縮
ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i+1

bit1 = BITbisect(Q+1) #傾き
bit2 = BITbisect(Q) #合計

b = 0
for q in range(Q):
    if Query[q][0] == 1:
        b += Query[q][2]
        a = Query[q][1]
        bit2.add(co_to_ind[a], a)
        bit1.add(1, -1)
        bit1.add(co_to_ind[a]+1, 2)
    else:
        i1 = bit1.search(0)
        a1 = ind_to_co[i1-1]
        #print(bit1.query_sum(i1), bit1.query_sum(1), bit1.query_sum(i1+1), bit1.query_sum(Q))
        delta = (bit1.query_sum(i1) - bit1.query_sum(1) + bit1.query_sum(i1+1) - bit1.query_sum(Q))//2
        a2 = bit2.query_sum(Q) - bit2.query_sum(i1-1) - bit2.query_sum(i1) + a1*delta + b
        print(a1, a2)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop, heappush

bigger = []
smaller = []

def modify(bigger, smaller, a: int, b: int, mid: int, ans: int):
    if not bigger and not smaller:
        heappush(smaller, -a)
        mid = a
    elif not bigger:
        if a < -smaller[0]:
            heappush(bigger, -heappop(smaller))
            heappush(smaller, -a)

            ans += abs(-smaller[0] - mid)

        else:
            heappush(bigger, a)
    else:
        if a < -smaller[0]:
            tmp = -heappop(smaller)
            heappush(smaller, -a)
            if (len(smaller) + len(bigger)) % 2:
                ans += abs(-smaller[0] - mid)
        elif a > bigger[0]:
            tmp = heappop(bigger)
            heappush(bigger, a)
        else:
            tmp = a

        if len(smaller) == len(bigger):
            heappush(smaller, -tmp)
        else:
            heappush(bigger, tmp)

    ans += (abs(-smaller[0] - a) + b)
    mid = -smaller[0]

    return mid, ans

q = ni()
mid = ans = 0

for _ in range(q):
    # judge process
    query = ns()
    if query.startswith("1"):
        _, a, b = map(int, query.split())
        mid, ans = modify(bigger, smaller, a, b, mid, ans)

    else:
        print(mid, ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

def main():
    INF = float("inf")

    sum_B = 0
    L, R = [INF], [INF]
    sum_L = sum_R = 0

    A = map(int, open(0).read().split())

    Q = next(A)
    for _ in range(Q):
        q = next(A)
        if q == 1:
            a, b = next(A), next(A)

            sum_B += b

            if len(L) > len(R):
                l = -L[0]
                if a >= l:
                    heappush(R, a)
                    sum_R += a
                else:
                    heappushpop(L, -a)
                    sum_L += a - l
                    heappush(R, l)
                    sum_R += l
            elif not L:
                heappush(R, a)
                sum_L += a
            else:
                r = R[0]
                if a <= r:
                    heappush(L, -a)
                    sum_L += a
                else:
                    heappushpop(R, a)
                    sum_R += a - r
                    heappush(L, -r)
                    sum_L += r

        else:
            median = -L[0]
            res = (median * len(L) - sum_L) + (sum_R - median * len(R)) + sum_B
            print(median, res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

def main():
    INF = 10 ** 18

    sum_B = 0
    L, R = [INF], [INF]
    sum_L = sum_R = 0

    A = map(int, open(0).read().split())

    Q = next(A)
    for _ in range(Q):
        q = next(A)
        if q == 1:
            a, b = next(A), next(A)

            sum_B += b

            if len(L) > len(R):
                l = -L[0]
                if a >= l:
                    heappush(R, a)
                    sum_R += a
                else:
                    heappushpop(L, -a)
                    sum_L += a - l
                    heappush(R, l)
                    sum_R += l
            elif len(L) == 0:
                heappush(R, a)
                sum_L += a
            else:
                r = R[0]
                if a <= r:
                    heappush(L, -a)
                    sum_L += a
                else:
                    heappushpop(R, a)
                    sum_R += a - r
                    heappush(L, -r)
                    sum_L += r

        else:
            median = -L[0]
            res = (median * len(L) - sum_L) + (sum_R - median * len(R)) + sum_B
            print(median, res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop, heappushpop

Q = int(readline())
query = (tuple(map(int,line.split())) for line in readlines())

# 適当に番兵を入れておく
INF = 10**12
L = [INF] # -1倍していれる
R = [INF]
sumL = 0; sumR = 0 # 和
lenL = 0; lenR = 0 # 長さ

add = 0 # 全体に共通に加わってるもの

answer = []
for q in query:
    if len(q) == 1:
        # 値を求める
        x = -L[0]
        f = sumR - sumL + x * (lenL - lenR)
        answer.append('{} {}'.format(x,f+add))
        continue
    # 更新
    a,b = q[1:]
    add += b
    if lenL > lenR:
        sumL += a; a = -heappushpop(L,-a); sumL -= a
        heappush(R,a); sumR += a; lenR += 1
    else:
        sumR += a; a = heappushpop(R,a); sumR -= a
        heappush(L,-a); sumL += a; lenL += 1

print('\n'.join(answer))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

Q = int(readline())
query = (tuple(map(int,line.split())) for line in readlines())

# 適当に番兵を入れておく
INF = 10**12
L = [INF] # -1倍していれる
R = [INF]
sumL = 0; sumR = 0 # 和
lenL = 0; lenR = 0 # 長さ

add = 0 # 全体に共通に加わってるもの

answer = []
for q in query:
    if len(q) == 1:
        # 値を求める
        x = -L[0]
        f = sumR - sumL + x * (lenL - lenR)
        answer.append('{} {}'.format(x,f+add))
        continue
    # 更新
    a,b = q[1:]
    add += b
    
    b = -heappop(L); sumL -= b
    c = heappop(R); sumR -= c
    a,b,c = sorted([a,b,c])
    heappush(L,-a); sumL += a
    heappush(R,c); sumR += c
    if lenL > lenR:
        heappush(R,b); sumR += b; lenR += 1
    else:
        heappush(L,-b); sumL += b; lenL += 1

print('\n'.join(answer))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

Q = int(readline())
query = (tuple(map(int,line.split())) for line in readlines())

# 適当に番兵を入れておく
INF = 10**12
L = [INF] # -1倍していれる
R = [INF]
SL = 0; SR = 0

add = 0 # 全体に共通に加わってるもの

answer = []
for q in query:
    if len(q) == 1:
        # 値を求める
        x = -L[0]
        f = SR - SL + x * (len(L)-len(R))
        answer.append('{} {}'.format(x,f+add))
        continue
    # 更新
    a,b = q[1:]
    add += b
    
    b = -heappop(L); SL -= b
    c = heappop(R); SR -= c
    a,b,c = sorted([a,b,c])
    heappush(L,-a); SL += a
    heappush(R,c); SR += c
    if len(L) > len(R):
        heappush(R,b); SR += b
    else:
        heappush(L,-b); SL += b

print('\n'.join(answer))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

Q = int(readline())
query = (tuple(map(int,line.split())) for line in readlines())

# 適当に番兵を入れておく
INF = 10**12
L = [INF] # -1倍していれる
R = [INF]
SL = 0; SR = 0

def pushL(x):
    global SL
    heappush(L,-x)
    SL += x
def popL():
    global SL
    x = -heappop(L)
    SL -= x
    return x
def pushR(x):
    global SR
    heappush(R,x)
    SR += x
def popR():
    global SR
    x = heappop(R)
    SR -= x
    return x

add = 0 # 全体に共通に加わってるもの

answer = []
for q in query:
    if len(q) == 1:
        # 値を求める
        x = -L[0]
        f = SR - SL + x * (len(L)-len(R))
        answer.append('{} {}'.format(x,f+add))
        continue
    # 更新
    a,b = q[1:]
    add += b
    b = popL(); c = popR()
    a,b,c = sorted([a,b,c])
    pushL(a); pushR(c)
    if len(L) > len(R):
        pushR(b)
    else:
        pushL(b)

print('\n'.join(answer))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
    INF = 10 ** 18

    sum_B = 0
    L, R = [INF], [INF]
    sum_L = sum_R = 0
    L_size = R_size = 0

    A = map(int, open(0).read().split())

    Q = next(A)
    for _ in range(Q):
        q = next(A)
        if q == 1:
            a, b = next(A), next(A)

            sum_B += b

            max_L = -heappop(L)
            min_R = heappop(R)

            sum_L -= max_L
            sum_R -= min_R

            l, m, r = sorted((max_L, a, min_R))

            heappush(L, -l)
            heappush(R, r)
            sum_L += l
            sum_R += r

            if L_size == R_size:
                heappush(L, -m)
                L_size += 1
                sum_L += m
            else:
                heappush(R, m)
                R_size += 1
                sum_R += m

        else:
            median = -L[0]
            min_value = sum_B + sum_R - sum_L
            if L_size != R_size:
                min_value += median
            print(median, min_value)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 18

sum_B = 0
L, R = [INF], [INF]
sum_L = sum_R = 0
L_size = R_size = 0

A = map(int, open(0).read().split())

Q = next(A)
for _ in range(Q):
    q = next(A)
    if q == 1:
        a, b = next(A), next(A)

        sum_B += b

        max_L = -heappop(L)
        min_R = heappop(R)

        sum_L -= max_L
        sum_R -= min_R

        l, m, r = sorted((max_L, a, min_R))

        heappush(L, -l)
        heappush(R, r)
        sum_L += l
        sum_R += r

        if L_size == R_size:
            heappush(L, -m)
            L_size += 1
            sum_L += m
        else:
            heappush(R, m)
            R_size += 1
            sum_R += m

    else:
        median = -L[0]
        min_value = sum_B + sum_R - sum_L
        if L_size != R_size:
            min_value += median
        print(median, min_value)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 18

sum_B = 0
L, R = [INF], [INF]
sum_L = sum_R = 0
L_size = R_size = 0

A = map(int, open(0).read().split())

Q = next(A)
for _ in range(Q):
    q = next(A)
    if q == 1:
        a, b = next(A), next(A)

        sum_B += b

        max_L = -heappop(L)
        min_R = heappop(R)

        sum_L -= max_L
        sum_R -= min_R

        l, m, r = sorted((max_L, a, min_R))
        if L_size == R_size:
            heappush(L, -l)
            heappush(L, -m)
            heappush(R, r)
            L_size += 1
            sum_L += l + m
            sum_R += r
        else:
            heappush(L, -l)
            heappush(R, m)
            heappush(R, r)
            R_size += 1
            sum_L += l
            sum_R += m + r
    else:
        median = -L[0]
        min_value = sum_B + sum_R - sum_L
        if L_size != R_size:
            min_value += median
        print(median, min_value)

Submission status: Accepted

Solution code:
# ABC140E
import sys
input = sys.stdin.readline
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

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

q=int(input())
xs = []
ys = []
qs = dict()
c = 0
for _ in range(q):
    xy = list(map(int,input().split()))
    if len(xy) == 1:
        if c not in qs:
            qs[c] = 0
        qs[c] += 1
    else:
        c += 1
        xs.append(xy[1])
        ys.append(xy[2])

N=len(xs)
sxs=sorted(xs)
zxs = [0]*N
for i, x in enumerate(sorted(range(N), key=lambda x : xs[x])):
    zxs[x] = i

seg_sum_tree = Bit(N)
seg_count_tree = Bit(N)

sy = 0
for i in range(c+1):
    if i in qs:
        x1i=bsearch(i//2 + (-1 if i % 2 == 0 else 0) ,0 ,N ,lambda x : seg_count_tree.sum(x))
#        print(x1i, i//2, seg_count_tree.query(0, 2))
        if i % 2:
        #print(sy, seg_sum_tree.query(0, x1i))
            r = sy - seg_sum_tree.sum(x1i) + \
                   seg_sum_tree.sum(N) - seg_sum_tree.sum(x1i+1)
        else:
            r = sy - seg_sum_tree.sum(x1i+1) + \
                   seg_sum_tree.sum(N) - seg_sum_tree.sum(x1i+1)
        for _ in range(qs[i]):
            print(sxs[x1i], r)
    if i == c:
        break
    x, y = xs[i], ys[i]
    xi = zxs[i]
    sy += y
    seg_sum_tree.add(xi+1, x)
    seg_count_tree.add(xi+1, 1)

Submission status: Accepted

Solution code:
# ABC140E
import sys
input = sys.stdin.readline
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

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

q=int(input())
xs = []
ys = []
qs = dict()
c = 0
for _ in range(q):
    xy = list(map(int,input().split()))
    if len(xy) == 1:
        if c not in qs:
            qs[c] = 0
        qs[c] += 1
    else:
        c += 1
        xs.append(xy[1])
        ys.append(xy[2])

N=len(xs)
sxs=sorted(xs)
zxs = [0]*N
for i, x in enumerate(sorted(range(N), key=lambda x : xs[x])):
    zxs[x] = i

seg_sum_tree = SegTree([0]*N, N, 0, lambda x, y: x+y)
#seg_count_tree = SegTree([0]*N, N, 0, lambda x, y: x+y)
seg_count_tree = Bit(N)

sy = 0
for i in range(c+1):
    if i in qs:
        x1i=bsearch(i//2 + (-1 if i % 2 == 0 else 0) ,0 ,N ,lambda x : seg_count_tree.sum(x))
#        print(x1i, i//2, seg_count_tree.query(0, 2))
        if i % 2:
        #print(sy, seg_sum_tree.query(0, x1i))
            r = sy - seg_sum_tree.query(0, x1i) + \
                   seg_sum_tree.query(x1i+1, N)
        else:
            r = sy - seg_sum_tree.query(0, x1i+1) + \
                   seg_sum_tree.query(x1i+1, N)
        for _ in range(qs[i]):
            print(sxs[x1i], r)
    if i == c:
        break
    x, y = xs[i], ys[i]
    xi = zxs[i]
    sy += y
    seg_sum_tree.update(xi, x)
    seg_count_tree.add(xi+1, 1)

Submission status: Accepted

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

def main():
    q = int(input())
    
    big = [10**10]
    sma = [10**10]
    sb = 0
    ss = 0

    rr = 0

    for _ in [None]*q:  
        m = tuple(map(int,input().split()))
        
        if m[0] == 1:
            a = m[1]
            rr += m[2]

            if big[0] <= a:
                heapq.heappush(big,a)
                sb += a
            elif -sma[0] >= a:
                heapq.heappush(sma,-a)
                ss += a
            elif len(sma) >= len(big):
                heapq.heappush(sma,-a)
                ss += a
            else:
                heapq.heappush(big,a)
                sb += a
            
            while len(big) > len(sma)+1:
                p = heapq.heappop(big)
                heapq.heappush(sma,-p)
                ss += p
                sb -= p
            
            while len(sma) >  len(big)+1:
                p = -heapq.heappop(sma)
                heapq.heappush(big,p)
                sb += p
                ss -= p
            
        else:
            if len(big) > len(sma):
                mid = big[0]
            else:
                mid = -sma[0]
            
            print(mid,sb-mid*(len(big)-1) + mid*(len(sma)-1) -ss +rr)

if __name__ =="__main__":
    main()

Submission status: Accepted

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

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])
                left_sum += cent_list[0]
                median = cent_list[0]
                heapq.heappush(right_list, source)
                right_sum += source
                cent_list.remove(cent_list[0])
            else:
                heapq.heappush(left_list, -source)
                left_sum += source
                median = -left_list[0]
                heapq.heappush(right_list, cent_list[0])
                right_sum += cent_list[0]
                cent_list.remove(cent_list[0])
            count += 1

    else:
        minval = np.abs(left_sum-count*median) + np.abs(right_sum-count*median) + intercept
        #print(str(median) + " " + str(minval))
        print("{} {}".format(median, minval))

Submission status: Accepted

Solution code:
from heapq import heappop
from heapq import heappush
q=int(input())
L,R=[],[]
b_sum=0
l_sum,r_sum=0,0
count=0
mid=0
for _ in range(q):
  
  Q=list(map(int,input().split()))
  if Q[0]==1:
    a,b=Q[1],Q[2]
    count+=1
    b_sum+=b
    if count==1:
      mid=a
    elif count%2==0:
      if a<=mid:
        heappush(L,-a)
        l_sum+=a
        heappush(R,mid)
        r_sum+=mid
      else:
        heappush(L,-mid)
        l_sum+=mid
        heappush(R,a)
        r_sum+=a
    else:
      l,r=-heappop(L),heappop(R)
      if a<l:
        heappush(L,-a)
        l_sum+=a-l
        mid=l
        heappush(R,r)
      elif r<a:
        heappush(L,-l)
        mid=r
        heappush(R,a)
        r_sum+=a-r
      else:
        heappush(L,-l)
        mid=a
        heappush(R,r)

  else:
    if count%2==1:
      print(mid,r_sum-l_sum+b_sum)
    else:
      l=-heappop(L)
      print(l,r_sum-l_sum+b_sum)
      heappush(L,-l)

Submission status: Accepted

Solution code:
import heapq
Q = int(input())
L = []
R = []
B = 0
n = 0
res = 0
for _ in range(1, Q + 1):
  q = input()
  if q == "2":
    print(-L[0], res + B)
  else:
    n += 1
    t, a, b = map(int, q.split())
    B += b
    if len(L) == 0 or a <= -L[0]:
      heapq.heappush(L, -a)
      res += -L[0] - a
    else:
      heapq.heappush(R, a)
      res += a + L[0]
    if len(R) > len(L):
      res -= R[0] + L[0]
      heapq.heappush(L, -heapq.heappop(R))
    elif len(L) - len(R) >= 2:
      heapq.heappush(R, -heapq.heappop(L))