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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(Q):
    sb = 0

    l = []
    sl = 0
    r = []
    sr = 0

    n = 0
    sa = 0
    for q in Q:
        if q[0] == 1:
            _, a, b = q
            sa += abs(a)
            heapq.heappush(l, -a)
            sl += a
            if len(l) > len(r) + 1:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a
            sb += b
            n += 1
        else:
            x = -l[0]
            print(x, abs(sl - len(l)*x) + abs(sr - len(r)*x) + sb)

def main():
    N = read_int()
    Q = [read_int_n() for _ in range(N)]
    slv(Q)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(Q):
    sb = 0

    l = []
    r = []

    n = 0
    sa = 0
    for q in Q:
        if q[0] == 1:
            _, a, b = q
            sa += abs(a)
            heapq.heappush(l, -a)
            if len(l) > len(r) + 1:
                heapq.heappush(r, -heapq.heappop(l))
            sb += b
            n += 1
        else:
            x = -l[0]
            if n % 2 == 0:
                print(x, sa - abs(x) * len(r) + sb)
            else:
                print(x, sa - abs(x) * n + sb)


def main():
    N = read_int()
    Q = [read_int_n() for _ in range(N)]
    slv(Q)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
Q=int(input())

alist=[]
hq_left,hq_right=[],[]
dummy,a1,b1=map(int,input().split())
heapq.heappush(hq_left,-a1)
heapq.heappush(hq_right,a1)
b=b1

min_arg=-hq_left[0]
min_diff=0
#min_value=b      
for _ in range(Q-1):
  query=list(map(int,input().split()))
  if len(query)==3:    
    dummy,ai,bi=query
    b+=bi
    
    max_left=-hq_left[0]
    min_right=hq_right[0]
    if ai<max_left:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_left,-ai)
      heapq.heappop(hq_left)
      heapq.heappush(hq_right,max_left)      
      min_diff=max_left-ai
    elif min_right<ai:
      heapq.heappush(hq_right,ai)
      heapq.heappush(hq_right,ai)
      heapq.heappop(hq_right)
      heapq.heappush(hq_left,-min_right)      
      min_diff=ai-min_right
    else:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_right,ai)      
      min_diff=0
  else:    
    min_arg=-hq_left[0]
    min_value=min_diff+b
    print(min_arg,min_value)

Submission status: Wrong Answer

Solution code:
import heapq
Q=int(input())

alist=[]
hq_left,hq_right=[],[]
dummy,a1,b1=map(int,input().split())
heapq.heappush(hq_left,-a1)
heapq.heappush(hq_right,a1)
b=b1

min_arg=-hq_left[0]
min_value=b      
for _ in range(Q-1):
  query=list(map(int,input().split()))
  if len(query)==3:    
    dummy,ai,bi=query
    b+=bi
    
    max_left=-hq_left[0]
    min_right=hq_right[0]
    if ai<max_left:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_left,-ai)
      heapq.heappop(hq_left)
      heapq.heappush(hq_right,max_left)
      
      min_arg=-hq_left[0]
      min_value=max_left-ai+b
    elif min_right<ai:
      heapq.heappush(hq_right,ai)
      heapq.heappush(hq_right,ai)
      heapq.heappop(hq_right)
      heapq.heappush(hq_left,-min_right)
      
      min_arg=-hq_left[0]
      min_value=ai-min_right+b
    else:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_right,ai)
      
      min_arg=-hq_left[0]
      min_value=b      
  else:
    print(min_arg,min_value)

Submission status: Wrong Answer

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

import heapq

Q = int(input())
totalB = 0
minimum = 0

INF = 10 ** 18

L_pque = []
R_pque = []

heapq.heappush(L_pque, +INF)
heapq.heappush(R_pque, +INF)

for _ in range(Q):
    tmp = tuple(map(str, input().split()))
    if len(tmp) == 1:
        print (-L_pque[0], minimum + totalB)
    else:
        a = int(tmp[1])
        b = int(tmp[2])

        totalB += b

        tmpA = -L_pque[0]
        tmpB = +R_pque[0]
        # print ('区間', tmpA, tmpB)

        if a < tmpA:
            minimum = abs(tmpA - a)
        elif tmpB < a:
            minimum = abs(a - tmpB)
        else:
            minimum = 0
        
        heapq.heappush(L_pque, -a)
        heapq.heappush(R_pque, +a)

        tmpA = -heapq.heappop(L_pque)
        tmpB = +heapq.heappop(R_pque)

        if tmpA <= tmpB:
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)
        else:
            tmpA, tmpB = tmpB, tmpA
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)

Submission status: Wrong Answer

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

import heapq

Q = int(input())
totalB = 0
minimum = 0

INF = 10 ** 18

L_pque = [INF]
R_pque = [INF]

for _ in range(Q):
    tmp = tuple(map(str, input().split()))
    if len(tmp) == 1:
        print (-L_pque[0], minimum + totalB)
    else:
        a = int(tmp[1])
        b = int(tmp[2])

        totalB += b

        tmpA = -L_pque[0]
        tmpB = +R_pque[0]

        if a < tmpA:
            minimum = abs(tmpA - a)
        elif tmpB < a:
            minimum = abs(a - tmpB)
        else:
            minimum = 0

        heapq.heappush(L_pque, -a)
        heapq.heappush(R_pque, +a)

        tmpA = -heapq.heappop(L_pque)
        tmpB = +heapq.heappop(R_pque)

        if tmpA <= tmpB:
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)
        else:
            tmpA, tmpB = tmpB, tmpA
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)

Submission status: Wrong Answer

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

import heapq

Q = int(input())
totalB = 0
minimum = 0

INF = 10 ** 18

L_pque = [INF]
R_pque = [INF]

for _ in range(Q):
    tmp = tuple(map(str, input().split()))
    if len(tmp) == 1:
        print (-L_pque[0], minimum + totalB)
    else:
        a = int(tmp[1])
        b = int(tmp[2])

        totalB += b

        tmpA = -L_pque[0]
        tmpB = +R_pque[0]

        if a < tmpA:
            minimum = abs(tmpA - a)
        elif tmpB < a:
            minimum = abs(a - tmpB)

        heapq.heappush(L_pque, -a)
        heapq.heappush(R_pque, +a)

        tmpA = -heapq.heappop(L_pque)
        tmpB = +heapq.heappop(R_pque)

        if tmpA <= tmpB:
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)
        else:
            tmpA, tmpB = tmpB, tmpA
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)

Submission status: Wrong Answer

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

import heapq

Q = int(input())
totalB = 0
minimum = 0

INF = 10 ** 18

L_pque = [INF]
R_pque = [INF]

for _ in range(Q):
    tmp = tuple(map(str, input().split()))
    if len(tmp) == 1:
        print (-L_pque[0], minimum + totalB)
    else:
        a = int(tmp[1])
        b = int(tmp[2])

        totalB += b

        tmpA = -L_pque[0]
        tmpB = +R_pque[0]

        if a < tmpA:
            minimum = abs(tmpA - a)
        elif tmpB < a:
            minimum = abs(a - tmpB)

        heapq.heappush(L_pque, -a)
        heapq.heappush(R_pque, +a)

        tmpA = -heapq.heappop(L_pque)
        tmpB = +heapq.heappop(R_pque)

        if tmpA <= tmpB:
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)
        else:
            tmpA, tmpB = tmpB, tmpA
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)

Submission status: Wrong Answer

Solution code:
import heapq

q = int(input())

nchange = 0
ming, maxg = [], []
heapq.heapify(ming)
heapq.heapify(maxg)
a = 0
b = 0
for i in range(q):
    qi = input()
    if qi[0] == '1':
        _, ai, bi = map(int, qi.split())
        b += bi
        nchange += 1
        if nchange % 2 == 1:
            if nchange == 1:
                x = ai
                continue
            Smax = -heapq.heappop(ming)
            Dmin = heapq.heappop(maxg)
            if Smax <= ai and ai <= Dmin:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, Dmin)
                x = ai
            elif ai < Smax:
                heapq.heappush(ming, -ai)
                heapq.heappush(maxg, Dmin)
                x = Smax
                a += Smax - ai
            else:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, ai)
                x = Dmin
                a += ai - Dmin
        else:
            heapq.heappush(ming, -min(x, ai))
            heapq.heappush(maxg, max(x, ai))
            a += abs(x - ai)
            x = min(x, ai)
    else:
        print(x, a+b)

Submission status: Wrong Answer

Solution code:
Q = int(input())
cnt = 0
m = []
M = []
import heapq
heapq.heapify(m)
heapq.heapify(M)
sum_m = 0
sum_M = 0
B = 0
cnt = 0
for i in range(Q):
    #print(m, M)
    q = str(input())
    if q != '2':
        _, a, b = map(int, q.split())
        B += b
        cnt += 1
        if len(m) != 0 and len(M) != 0:
            x1 = heapq.heappop(m)*(-1)
            x2 = heapq.heappop(M)
            sum_m -= x1
            sum_M -= x2
            if a <= x2:
                heapq.heappush(m, a*(-1))
                heapq.heappush(m, x1*(-1))
                sum_m += a+x1
                heapq.heappush(M, x2)
                sum_M += x2
            else:
                heapq.heappush(M, a)
                sum_M += a
                heapq.heappush(m, x1*(-1))
                heapq.heappush(M, x2*(-1))
                sum_m += x1+x2
        elif len(m) != 0 and len(M) == 0:
            x1 = heapq.heappop(m)*(-1)
            sum_m -= x1
            if a <= x1:
                heapq.heappush(m, a*(-1))
                sum_m += a
                heapq.heappush(M, x1)
                sum_M += x1
            else:
                heapq.heappush(M, a)
                sum_M += a
                heapq.heappush(m, x1*(-1))
                sum_m += x1
        else:
            heapq.heappush(m, a*(-1))
            sum_m += a
    else:
        if cnt == 0:
            print(0, 0)
        else:
            m_ = len(m)
            M_ = len(M)
            x = heapq.heappop(m)*(-1)
            min_ = sum_M - sum_m + m_*x - M_*x + B
            #print(sum_M, sum_m, B)
            print(x, min_)
            heapq.heappush(m, x*(-1))

Submission status: Wrong Answer

Solution code:
Q = int(input())
cnt = 0
m = []
M = []
import heapq
heapq.heapify(m)
heapq.heapify(M)
sum_m = 0
sum_M = 0
B = 0
cnt = 0
for i in range(Q):
    q = str(input())
    if q != '2':
        _, a, b = map(int, q.split())
        B += b
        cnt += 1
        if len(m) != 0 and len(M) != 0:
            x1 = heapq.heappop(m)*(-1)
            x2 = heapq.heappop(M)
            sum_m -= x1
            sum_M -= x2
            if a <= x1:
                heapq.heappush(m, a*(-1))
                sum_m += a
                heapq.heappush(M, x1)
                heapq.heappush(M, x2)
                sum_M += x1+x2
            else:
                heapq.heappush(M, a)
                sum_M += a
                heapq.heappush(m, x1*(-1))
                heapq.heappush(M, x2*(-1))
                sum_m += x1+x2
        elif len(m) != 0 and len(M) == 0:
            x1 = heapq.heappop(m)*(-1)
            sum_m -= x1
            if a <= x1:
                heapq.heappush(m, a*(-1))
                sum_m += a
                heapq.heappush(M, x1)
                sum_M += x1
            else:
                heapq.heappush(M, a)
                sum_M += a
                heapq.heappush(m, x1*(-1))
                sum_m += x1
        else:
            heapq.heappush(m, a*(-1))
            sum_m += a
    else:
        if cnt%2 == 1:
            x = heapq.heappop(m)*(-1)
            min_ = sum_M+sum_m+B-x*cnt
            print(x, min_)
            heapq.heappush(m, x*(-1))
        else:
            if cnt == 0:
                print(0, 0)
            else:
                x = heapq.heappop(m)*(-1)
                min_ = sum_M+sum_m+B-x*cnt
                #print(sum_M, sum_m, B)
                print(x, min_)
                heapq.heappush(m, x*(-1))

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
q=int(input())
queries=[list(map(int,input().split()))for _ in range(q)]
l=[]
r=[]
ans=0
quecount=0
for query in queries:
  if query[0]==1:
    quecount+=1
    _,a,b=query
    ans+=b
    if quecount==1:
      mid=a
    elif quecount%2==1:
      if a<-l[0]:
        mid=-heappop(l)
        heappush(l,-a)
      elif r[0]<a:
        mid=heappop(r)
        heappush(r,a)
      else:
        mid=a
    else:
      ans+=abs(a-mid)
      heappush(l,-min(a,mid))
      heappush(r,max(a,mid))
  if query[0]==2:
    if quecount%2==1:
      ansind=mid
    else:
      ansind=-l[0]
    print(ansind,ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
q=int(input())
queries=[list(map(int,input().split()))for _ in range(q)]
l=[]
r=[]
ans=0
quecount=0
for query in queries:
  if query[0]==1:
    quecount+=1
    _,a,b=query
    ans+=b
    if quecount==1:
      mid=a
    elif quecount%2==1:
      if a<-l[0]:
        mid=-heappop(l)
        heappush(l,-a)
      elif r[0]<a:
        mid=heappop(r)
        heappush(r,a)
    else:
      ans+=abs(a-mid)
      heappush(l,-min(a,mid))
      heappush(r,max(a,mid))
  if query[0]==2:
    if quecount%2==1:
      ansind=mid
    else:
      ansind=-l[0]
    print(ansind,ans)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    q=int(input())
    Q=[tuple(map(int, input().split())) for _ in range(q)]
    asum=bsum=lsum=ssum=0
    from heapq import heappop, heappush
    s,l=[],[]
    for query in Q:
        if query[0]==1:
            a,b=query[1],query[2]
            bsum+=b
            E=[a]
            if s:
                smx=-heappop(s)
                ssum-=smx
                E.append(smx)
            if l:
                lmn=heappop(l)
                lsum-=lmn
                E.append(lmn)
            E.sort()
            for e in E:
                if len(s)<=len(l):
                    heappush(s,-e)
                    ssum+=e
                else:
                    heappush(l,e)
                    lsum+=e
        else:
            m=-s[0] if len(s)>len(l) else (-s[0]+l[0])/2
            print(m, m*len(s)-ssum + lsum-m*len(l) + bsum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    q=int(input())
    Q=[tuple(map(int, input().split())) for _ in range(q)]
    asum=bsum=lsum=ssum=0
    from heapq import heappop, heappush
    s,l=[],[]
    for query in Q:
        if query[0]==1:
            a,b=query[1],query[2]
            bsum+=b
            E=[a]
            if s:
                smx=-heappop(s)
                ssum-=smx
                E.append(smx)
            if l:
                lmn=heappop(l)
                lsum-=lmn
                E.append(lmn)
            E.sort()
            for e in E:
                if len(s)<=len(l):
                    heappush(s,-e)
                    ssum+=e
                else:
                    heappush(l,e)
                    lsum+=e
        else:
            m=-s[0]
            print(m, m*len(s)-ssum + lsum-m*len(l) + bsum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    q=int(input())
    Q=[tuple(map(int, input().split())) for _ in range(q)]
    asum=bsum=0
    count=0
    from heapq import heappop, heappush
    s,l=[],[]
    for query in Q:
        if query[0]==1:
            a,b=query[1],query[2]
            asum+=a
            bsum+=b
            count+=1
            if len(s)==0:
                s.append(-a)
            elif len(l)==0:
                if -s[0]<=a:
                    l.append(a)
                else:
                    l.append(-s.pop())
                    s.append(-a)
            else:
                E=[-heappop(s),heappop(l),a]
                E.sort()
                for e in E:
                    if len(s)<=len(l):
                        heappush(s,-e)
                    else:
                        heappush(l,e)
        else:
            print(-s[0], asum+count*s[0] +bsum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
Q = int(input())
cnt = 0
m = []
M = []
import heapq
heapq.heapify(m)
heapq.heapify(M)
sum_m = 0
sum_M = 0
B = 0
cnt = 0
for i in range(Q):
    q = str(input())
    if q != '2':
        _, a, b = map(int, q.split())
        B += b
        cnt += 1
        if len(m) != 0 and len(M) != 0:
            x1 = heapq.heappop(m)*(-1)
            x2 = heapq.heappop(M)
            sum_m -= x1
            sum_M -= x2
            if a <= x1:
                heapq.heappush(m, a*(-1))
                sum_m += a
                heapq.heappush(M, x1)
                heapq.heappush(M, x2)
                sum_M += x1+x2
            else:
                heapq.heappush(M, a)
                sum_M += a
                heapq.heappush(m, x1*(-1))
                heapq.heappush(M, x2*(-1))
                sum_m += x1+x2
        elif len(m) != 0 and len(M) == 0:
            x1 = heapq.heappop(m)*(-1)
            sum_m -= x1
            if a <= x1:
                heapq.heappush(m, a*(-1))
                sum_m += a
                heapq.heappush(M, x1)
                sum_M += x1
            else:
                heapq.heappush(M, a)
                sum_M += a
                heapq.heappush(m, x1*(-1))
                sum_m += x1
        else:
            heapq.heappush(m, a*(-1))
            sum_m += a
    else:
        if cnt%2 == 1:
            x = heapq.heappop(m)*(-1)
            print(x, B)
            heapq.heappush(m, x*(-1))
        else:
            if cnt == 0:
                print(0, 0)
            else:
                x = heapq.heappop(m)*(-1)
                min_ = sum_M-sum_m+B
                #print(sum_M, sum_m, B)
                print(x, min_)
                heapq.heappush(m, x*(-1))

Submission status: Wrong Answer

Solution code:
import sys
import time
import heapq

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    import bisect
    q = int(input())
    left = PriorityQueue([-INF], desc=True)
    right = PriorityQueue([INF])
    const = 0
    cur_f = 0
    length = 0

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            length += 1
            new_a = val[1]
            const += val[2]
            l = left.top()
            r = right.top()
            cur_x = l
            if length % 2 == 1:
                if new_a < l:
                    right.push(left.top())
                    left.push(new_a)
                    cur_f += abs(cur_x - new_a)
                elif new_a <= r:
                    left.push(new_a)
                    right.push(new_a)
                else:
                    left.push(right.top())
                    right.push(new_a)
                    cur_f += abs(cur_x - new_a)
            else:
                if new_a < l:
                    left.pop()
                    left.push(new_a)
                    cur_f += abs(cur_x - new_a)
                else:
                    right.pop()
                    right.push(new_a)
                    cur_f += abs(cur_x - new_a)
        else:
            print(left.top(), cur_f + const)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import time
import heapq

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    import bisect
    q = int(input())
    left = PriorityQueue([-INF], desc=True)
    right = PriorityQueue([INF])
    const = 0
    length = 0
    cur_x = 0
    cur_f = 0
    lc = 0
    rc = 0

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            new_a = val[1]
            const += val[2]
            length += 1
            cur_x = left.top()
            l = left.top()
            r = right.top()
            if lc > rc:
                rc += 1
                if new_a <= l:
                    right.push(left.pop())
                    left.push(new_a)
                    cur_f += abs(cur_x - new_a)
                elif new_a <= r:
                    right.push(new_a)
                else:
                    right.push(new_a)
                    cur_f += abs(cur_x - new_a)
            else:
                lc += 1
                if new_a <= l:
                    left.push(new_a)
                    cur_f += abs(cur_x - new_a)
                elif new_a <= r:
                    left.push(new_a)
                else:
                    left.push(right.pop())
                    right.push(new_a)
                    cur_f += abs(cur_x - new_a)

        if val[0] == 2:
            print(left.top(), cur_f + const)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import time
import heapq

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    import bisect
    q = int(input())
    left = PriorityQueue([-INF], desc=True)
    right = PriorityQueue([INF])
    const = 0
    length = 0
    cur_x = 0
    cur_f = 0

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            new = val[1]
            const += val[2]
            length += 1
            l = left.top()
            r = right.top()
            if l <= new <= r:
                left.push(new)
            if new < l:
                right.push(left.pop())
                left.push(new)
                cur_f += min(abs(l - new), abs(r - new))
            if new > r:
                left.push(right.pop())
                right.push(new)
                cur_f += min(abs(l - new), abs(r - new))
        if val[0] == 2:
            print(left.top(), cur_f + const)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import time
import heapq

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    import bisect
    q = int(input())
    left = PriorityQueue([-INF], desc=True)
    right = PriorityQueue([INF])
    const = 0
    length = 0
    cur_x = 0
    cur_f = 0

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            new = val[1]
            const += val[2]
            length += 1
            l = left.top()
            r = right.top()
            if l <= new <= r:
                left.push(new)
            if new < l:
                right.push(left.pop())
                left.push(new)
                cur_f += abs(right.top() - new)
            if new > r:
                left.push(right.pop())
                right.push(new)
                cur_f += abs(left.top() - new)
        if val[0] == 2:
            print(left.top(), cur_f + const)


if __name__ == '__main__':
    main()