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:
import bisect
import heapq
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class v:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def update(S, L, M):
    _, a, b = S
    M[0] += b

    if len(L[0]) == len(L[1]):
        r0 = 0 if len(L[0]) == 0 else -1 * L[0][0]

        if len(L[1]) == 0 or a <= L[1][0]:
            heapq.heappush(L[0], -a)
            r1 = -1 * L[0][0]
            d = r1 - r0

            M[1] += d * (len(L[0]) - 1)
            M[1] += r1 - a
            M[2] += d * len(L[1])
        else:
            t = heapq.heappushpop(L[1], a)
            heapq.heappush(L[0], -t)
            r1 = -1 * L[0][0]
            d = r1 - r0
            M[1] += d * (len(L[0]) - 1)
            M[1] += r1 - t
            M[2] -= t - r0
            M[2] -= d * (len(L[1]) - 1)
            M[2] += a - r1

    else:
        r0 = 0 if len(L[0]) == 0 else -1 * L[0][0]
        if r0 <= a:
            heapq.heappush(L[1], a)
            M[2] += a + L[0][0]

        else:
            heapq.heappush(L[0], -a)
            t = -1 * heapq.heappop(L[0])
            heapq.heappush(L[1], t)

            r1 = -1 * L[0][0]
            d = r1 - r0

            M[1] += d * (len(L[0]) - 1)
            M[1] += r1 - a
            M[2] -= d * (len(L[1]) - 1)
            M[2] += t - r1
    # print(L, M)


def print_min(L, M):
    print(-1 * L[0][0], sum(M))


def main():
    Q = int(input())

    L = [[], []]
    M = [0, 0, 0]
    for q in range(Q):
        S = read_list()
        if S[0] == 1:
            update(S, L, M)
        else:
            print_min(L, M)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class v:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def update(S, L, M):
    _, a, b = S
    M[0] += b

    if len(L[0]) == len(L[1]):
        r0 = 0 if len(L[0]) == 0 else -1 * L[0][0]
        heapq.heappush(L[0], -a)
        r1 = -1 * L[0][0]
        d = r1 - r0

        M[1] += d * (len(L[0]) - 1)
        M[1] += r1 - a
        M[2] += d * len(L[1])
    else:
        r0 = 0 if len(L[0]) == 0 else -1 * L[0][0]
        if r0 <= a:
            heapq.heappush(L[1], a)
            M[2] += a + L[0][0]

        else:
            heapq.heappush(L[0], -a)
            t = -1 * heapq.heappop(L[0])
            heapq.heappush(L[1], t)

            r1 = -1 * L[0][0]
            d = r1 - r0

            M[1] += d * (len(L[0]) - 1)
            M[1] += r1 - a
            M[2] += d * (len(L[1]) - 1)
            M[2] += t - r1


def print_min(L, M):
    print(-1 * L[0][0], sum(M))


def main():
    Q = int(input())

    L = [[], []]
    M = [0, 0, 0]
    for q in range(Q):
        S = read_list()
        if S[0] == 1:
            update(S, L, M)
        else:
            print_min(L, M)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class v:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def update(S, L, M):
    _, a, b = S

    r0 = 0 if len(L[0]) == 0 else -1 * L[0][0]
    heapq.heappush(L[0], -a)
    t = None
    if len(L[0]) - len(L[1]) >= 2:
        t = -1 * heapq.heappop(L[0])
        heapq.heappush(L[1], t)

    r1 = -1 * L[0][0]
    d = r1 - r0

    M[0] += b
    M[1] += d * (len(L[0]) - 1)
    M[1] += r1 - a
    M[2] += d * (len(L[1]) - (0 if t is None else 1))
    M[2] += 0 if t is None else t - r1
    # print((a, b), L, M)


def print_min(L, M):
    print(-1 * L[0][0], sum(M))


def main():
    Q = int(input())

    L = [[], []]
    M = [0, 0, 0]
    for q in range(Q):
        S = read_list()
        if S[0] == 1:
            update(S, L, M)
        else:
            print_min(L, M)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())
l = []
r = []
lsum = 0
rsum = 0
cnt = 0
b = 0
mid = 0
for i in range(q):
    *que,= map(int, input().split( ))
    if que[0]==1:
        b += que[2]
        a = que[1]
        ax = None
        if cnt%2:
            rsum += a
            heapq.heappush(r,a)
            ax = heapq.heappop(r)
            rsum -= ax
            heapq.heappush(l,ax)
            lsum += ax
        else:
            lsum += a
            heapq.heappush(l,a)
            ax = heapq.heappop(l)
            lsum -= a
            heapq.heappush(r,ax)
            rsum += ax
        cnt += 1
        mid = ax
    else:
        print(mid, b + rsum - lsum - (cnt%2)*mid)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 座圧（val→key）
def compress(A,reduction=True):
    if reduction:
        sorted_A = sorted(set(A))
    else:
        sorted_A = sorted(A)
    Adict = {val:key for key,val in enumerate(sorted_A)}
    return Adict,len(sorted_A),sorted_A

# Binary Indexed Tree（１点加算）
## 1-indexed
class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

Q = I()
query = []
for _ in range(Q):
    query.append(list(map(int,(input().split()))))

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

comp,n,values = compress(values,reduction=True)

# 位置の管理用
bit1 = BIT(n)

# 和の管理用
bit2 = BIT(n)

cumb = 0
num = 0
for i in range(Q):
    if query[i][0] == 1:
        cumb += query[i][2]
        val = query[i][1]
        num += 1
        p = comp[val]
        bit1.add(p+1,1)
        bit2.add(p+1,val)
    else:
        if num%2 == 1:
            med = bit1.search((num+1)//2)
            sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
            print(values[med-1],sum_+cumb)
        else:
            med = bit1.search(num//2)
            right = bit1.search(num//2+1)
            sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
            if med == right:
                print(values[med-1],sum_+cumb)
            else:
                print(values[med-1],sum_+cumb-values[med-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 座圧（val→key）
def compress(A,reduction=True):
    if reduction:
        sorted_A = sorted(set(A))
    else:
        sorted_A = sorted(A)
    Adict = {val:key for key,val in enumerate(sorted_A)}
    return Adict,len(sorted_A),sorted_A

# Binary Indexed Tree（１点加算）
## 1-indexed
class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

Q = I()
query = []
for _ in range(Q):
    query.append(list(map(int,(input().split()))))

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

comp,n,values = compress(values)

# 位置の管理用
bit1 = BIT(n)

# 和の管理用
bit2 = BIT(n)

cumb = 0
num = 0
for i in range(Q):
    if query[i][0] == 1:
        cumb += query[i][2]
        num += 1
        val = query[i][1]
        p = comp[val]
        bit1.add(p+1,1)
        bit2.add(p+1,val)
    else:
        if num%2 == 1:
            med = bit1.search((num+1)//2)
            sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
            print(values[med-1],sum_+cumb)
        else:
            med = bit1.search(num//2)
            sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
            print(values[med-1],sum_+cumb-values[med-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 座圧（val→key）
def compress(A,reduction=True):
    if reduction:
        sorted_A = sorted(set(A))
    else:
        sorted_A = sorted(A)
    Adict = {val:key for key,val in enumerate(sorted_A)}
    return Adict,len(sorted_A),sorted_A

# Binary Indexed Tree（１点加算）
## 1-indexed
class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

Q = I()
query = []
for _ in range(Q):
    query.append(list(map(int,(input().split()))))

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

comp,n,values = compress(values,reduction=False)

# 位置の管理用
bit1 = BIT(n)

# 和の管理用
bit2 = BIT(n)

cumb = 0
num = 0
for i in range(Q):
    if query[i][0] == 1:
        cumb += query[i][2]
        num += 1
        val = query[i][1]
        p = comp[val]
        bit1.add(p+1,1)
        bit2.add(p+1,val)
    else:
        if num%2 == 1:
            med = bit1.search((num+1)//2)
            sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
            print(values[med-1],sum_+cumb)
        else:
            med = bit1.search(num//2)
            sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
            print(values[med-1],sum_+cumb-values[med-1])

Submission status: Wrong Answer

Solution code:
Q=int(input())
import numpy as np
_,a,b=map(int,input().split())
A=np.array([a])
B=b
Nmid=0
ans=0
for i in range(Q-1):
  query=list(map(int,input().split()))
  if query[0]==1:
    ap=np.searchsorted(A,query[1])
    if ap<=Nmid:
      A=np.insert(A, ap, query[1])
      B+=query[2]
      if len(A)%2==0:
        ans+=(A[Nmid+1]-A[Nmid])*(len(A)-1-2*Nmid)
        ans+=A[Nmid]-query[1]
      else:
        Nmid+=1
        ans+=A[Nmid]-query[1]
    else:
      A=np.insert(A, ap, query[1])
      B+=query[2]
      if len(A)%2==1:
        Nmid+=1
        ans+=(A[Nmid]-A[Nmid-1])*(Nmid)
        if ap==Nmid:
          ans-=(A[Nmid]-A[Nmid-1])*(Nmid)
        else:
          ans-=(A[Nmid]-A[Nmid-1])*(Nmid-1)
        ans+=A[Nmid]-query[1]
      else:
        ans+=A[Nmid]-query[1]
  else:
    print(A[Nmid],ans+B)

Submission status: Wrong Answer

Solution code:
Q=int(input())
import heapq
A=[]
B=0
for i in range(Q):
  query=list(map(int,input().split()))
  if query[0]==1:
    heapq.heappush(A,query[1])
    B+=query[2]
  else:
    x=A[(len(A)-1)//2]
    ans=sum([abs(x-a) for a in A])+B
    print(x,ans)

Submission status: Wrong Answer

Solution code:

"""
灘入試コンのあれに似てる？？

bはあんまり関係ない

n回更新したとする
最小xの答えは左からn//2番目のa

f(x) = すべてのb + 他のaとの差の合計

一つ追加しても左右に1つ移動するだけ
→左右にあるaの数でb以外部分の変化を計算できる

→数列中に挿入が高速にできる必要がある？

二つのヒープを使って調整する？
いけそう

"""

import heapq

numQ = int(input())
bsum = 0

Lheap = [] #最大値を出す→負
Rheap = [] #最小値、正

for loop in range(numQ):

    query = input()

    if query == "2":

        print (nx , fx + bsum)

    else:

        query , newa , newb = query.split()
        newa = int(newa)
        newb = int(newb)

        bsum += newb

        if loop == 0:

            nx = newa
            fx = 0
            heapq.heappush(Lheap , -1 * newa)

        else:

            #ヒープの移動を行う→数字をいじるでokそう

            fx += abs(nx - newa)


            if -1 * Lheap[0] > newa:

                heapq.heappush(Lheap , -1 * newa)

            else:

                heapq.heappush(Rheap , newa)

            


            while len(Lheap) > len(Rheap) + 1:

                temp = heapq.heappop(Lheap)
                heapq.heappush(Rheap , -1 * temp)

            while len(Rheap) > len(Lheap):

                temp = heapq.heappop(Rheap)
                heapq.heappush(Lheap, -1 * temp)

            ox = nx

            nx = -1 * Lheap[0]

            
            #print (Lheap,Rheap)
            fx += (ox-nx) * ( len(Rheap) - len(Lheap))

Submission status: Wrong Answer

Solution code:

"""
灘入試コンのあれに似てる？？

bはあんまり関係ない

n回更新したとする
最小xの答えは左からn//2番目のa

f(x) = すべてのb + 他のaとの差の合計

一つ追加しても左右に1つ移動するだけ
→左右にあるaの数でb以外部分の変化を計算できる

→数列中に挿入が高速にできる必要がある？

二つのヒープを使って調整する？
いけそう

"""

import heapq

numQ = int(input())
bsum = 0

Lheap = [] #最大値を出す→負
Rheap = [] #最小値、正

for loop in range(numQ):

    query = input()

    if query == "2":

        print (nx , fx + bsum)

    else:

        query , newa , newb = query.split()
        newa = int(newa)
        newb = int(newb)

        bsum += newb

        if loop == 0:

            nx = newa
            fx = 0
            heapq.heappush(Lheap , -1 * newa)

        else:

            #ヒープの移動を行う→数字をいじるでokそう

            fx += abs(nx - newa)


            if -1 * Lheap[0] > newa:

                heapq.heappush(Lheap , -1 * newa)

            else:

                heapq.heappush(Rheap , newa)

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())
a_smalls = []
a_larges = []
b_sum = 0
for _ in range(q):
  query = map(int, input().split())
  if next(query) == 1:
    a, b = query
    a_s = -heapq.heappushpop(a_smalls, -a)
    a_l = heapq.heappushpop(a_larges, a)
    if a_s > a_l:
      a_s, a_l = a_l, a_s
    heapq.heappush(a_smalls, -a_s)
    heapq.heappush(a_larges, a_l)
    b_sum += b
  else:
    print(-a_smalls[0], b_sum + a_larges[0] + a_smalls[0])

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())
a_mins = []
a_maxs = []
b_sum = 0
for _ in range(q):
  query = map(int, input().split())
  if next(query) == 1:
    a, b = query
    a_min = -heapq.heappushpop(a_mins, -a)
    a_max = heapq.heappushpop(a_maxs, a)
    a_min, a_max = sorted([a_min, a_max])
    heapq.heappush(a_mins, -a_min)
    heapq.heappush(a_maxs, a_max)
    b_sum += b
  else:
    print(-a_mins[0], b_sum + a_maxs[0] + a_mins[0])

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())
a_mins = []
a_maxs = []
b_sum = 0
for _ in range(q):
  query = map(int, input().split())
  if next(query) == 1:
    a, b = query
    a_min = -heapq.heappushpop(a_mins, -a)
    a_max = heapq.heappushpop(a_maxs, a)
    a_min, a_max = sorted([a_min, a_max])
    heapq.heappush(a_mins, -a_min)
    heapq.heappush(a_maxs, a_max)
    b_sum += b
  else:
    print(a_maxs[0], b_sum + a_maxs[0] + a_mins[0])

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop, heappushpop 

n = int(sys.stdin.readline().rstrip())
Q = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
def main():
    c = 0
    res = 0
    lo, hi = [], []
    m_x = None
    for q in Q:
        if len(q) == 3:
            a, b = q[1:]
            c += b
            if not lo:
                heappush(lo, -a)
                m_x = a
                continue
            if len(lo) == len(hi):
                l, r = -heappop(lo), heappop(hi)
                heappush(lo, -l)
                if a <= r:
                    heappush(lo, -a)
                    heappush(hi, r)
                    if a >= l:
                        m_x = a
                    else:
                        res += l - a
                else:
                    res += a - r
                    heappush(lo, -r)
                    heappush(hi, a)
                    m_x = r
            else:
                l = -heappop(lo)
                if a >= l:
                    heappush(lo, -l)
                    heappush(hi, a)
                else:
                    heappush(lo, -a)
                    heappush(hi, l)
                    m_x = a
                res += abs(l - a)
        else:
            yield m_x, res + c

if __name__ == '__main__':
    ans = main()
    for a in ans:
        print(*a, sep=' ')

Submission status: Wrong Answer

Solution code:

if __name__ == '__main__':
    Q=int(input())
    A=[]
    B=[]
    mini=0
    pre_range=None
    for i in range(Q):
        query=list(map(int,input().split()))
        if query[0]==1:
            A.append(query[1])
            B.append(query[2])
            mini+=query[2]
        else:
            A.sort()
            left=A[:len(A)//2]
            right=A[len(A)//2:]
            if len(A)==1:
                print("{} {}".format(A[0],B[0]))
                pre_range = [A[0],A[0]]
            else:
                range=[left[-1],right[0]]
                if pre_range is None:
                    pre_range=range
                else:
                    if pre_range[0]<=range[0]<=pre_range[1]:
                        continue
                    else:
                        mini+=min(abs(range[0]-pre_range[0]),abs(range[0]-pre_range[1]))
                print("{} {}".format(range[0],mini))

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())
inf = 10000000000
left = [inf]
right = [inf]
minval = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, a, b = query
        if a < -left[0]:
            v = -heapq.heappop(left)
            heapq.heappush(right, v)
            heapq.heappush(left, -a)
            heapq.heappush(left, -a)
            minval += abs(v - a) + b
        elif a > right[0]:
            v = heapq.heappop(right)
            heapq.heappush(left, -v)
            heapq.heappush(right, a)
            heapq.heappush(right, a)
            minval += abs(v - a) + b
        else:
            heapq.heappush(left, -a)
            heapq.heappush(right, a)
            minval += b
    else:
        print(-left[-1], minval)

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())
inf = 10000000000
left = [inf]
right = [inf]
minval = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, a, b = query
        if a < -left[0]:
            v = -heapq.heappop(left)
            heapq.heappush(right, v)
            heapq.heappush(left, -a)
            heapq.heappush(left, -a)
            minval += abs(v - a) + b
        elif a > right[0]:
            v = heapq.heappop(right)
            heapq.heappush(left, -v)
            heapq.heappush(right, a)
            heapq.heappush(right, a)
            minval += abs(v - a) + b
        else:
            heapq.heappush(left, -a)
            heapq.heappush(right, a)
            minval += b
    else:
        print(right[0], minval)

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())

minheap = [] # right
maxheap = [] # left
heapq.heapify(minheap)
heapq.heapify(maxheap)

s = 0
m = 0

for _ in range(0, q):
    token = input().split()
    if len(token) > 1:
        a = int(token[1])
        b = int(token[2])
        print(a, b)
        s += b
        heapq.heappush(minheap, a)
        heapq.heappush(maxheap, -a)
        if -maxheap[0] > minheap[0]:
            maxv = -heapq.heappop(maxheap)
            minv = heapq.heappop(minheap)
            m += abs(maxv - minv)
            heapq.heappush(minheap, maxv)
            heapq.heappush(maxheap, -minv)
    else:
        print('{} {}'.format(-maxheap[0], s + m))

Submission status: Wrong Answer

Solution code:
q=int(input())
a=[]
b = 0

def query2(a,b,x):
    ret = b
    for sa in a:
        ret += abs(x-sa)
    return ret


for _ in range(q):
    x=list(map(int,input().split()))
    if x[0] ==1:
        a.append(x[1])
        b += x[2]
    elif x[0] == 2:
        r1 = a[(len(a)-1)//2]
        r2 = query2(a,b,r1)
        print(str(r1)+" "+str(r2))

Submission status: Wrong Answer

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
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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(set(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:
        center_ind = bit1.search(n // 2 + bool(n % 2))
        d = n // 2 + bool(n % 2)
        min_val = bit2.interval_sum(center_ind + 1, n) - bit1.interval_sum(center_ind + 1, n) * ind_to_co[center_ind] \
                  + bit1.sum(center_ind - 1) * ind_to_co[center_ind] - bit2.sum(center_ind - 1) + B
        print(ind_to_co[center_ind], min_val)