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:
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)
        print(min_ind)
        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: Wrong Answer

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)
        else:
            heappush(bigger, a)
    else:
        if a < -smaller[0]:
            tmp = -heappop(smaller)
            heappush(smaller, -a)
        else:
            tmp = heappop(bigger)
            heappush(bigger, a)

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

    ans += (abs(-smaller[0] - mid) + 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: Wrong Answer

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

class BIT():
    def __init__(self, max):
        self.max = max + 1
        self.data = [0]*(self.max)
    
    # 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 <= Q:
            self.data[i] += x
            i += i & -i
    
    # x以上にならないギリギリライン
    def search(self, x):
        l = 0
        r = self.max+1
        while r - l > 1:
            m = (l+r)//2
            if self.query_sum(m) >= x:
                r = m
            else:
                l = m
        return l
    

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

bit1 = BIT(Q+1) #傾き
bit2 = BIT(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]
        a2 = bit2.query_sum(Q) - bit2.query_sum(i1-1) - bit2.query_sum(i1) + b
        if i1 < len(A): a2 -= a1
        print(a1, a2)

Submission status: Wrong Answer

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

sy = 0
for i in range(c+1):
    if i in qs:
        x1i=x2i=bsearch(i//2 ,0 ,N-1 ,lambda x : seg_count_tree.query(0, x))
#        print(x1i, i//2, seg_count_tree.query(0, 2))
        if i % 2:
            x2i = x1i + 1
        #print(sy, seg_sum_tree.query(0, x1i))
        r = sy - seg_sum_tree.query(0, x1i) + \
               seg_sum_tree.query(x2i, 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.update(xi, 1)

Submission status: Wrong Answer

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

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

    _, a, b = query[0]
    A = [a]
    middle = 0
    ans = b
    for i in range(1, Q):
        if query[i][0] == 1:# 更新クエリ
            _, a, b = query[i]
            pre_x = A[middle]
            ans += b + abs(pre_x - a)
            bisect.insort_left(A, a)
            # print("kyuti:", A, middle, ans)
            if len(A)&1:
                middle += 1
                ans += abs(pre_x - A[middle])
        else:# 求値クエリ
            print(A[middle], ans)
        # print(i, "ans:", ans, "middle:", A[middle], "A:", A)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
Q = int(input())
Qlist = [list(map(int,input().split())) for i in range(Q)]
#print(Qlist)
coef_list = []
intercept = [0]
left_list = []
cent_list = []
right_list = []
left_sum = [0]
right_sum = [0]

median = [0]
count = [0,0]

def update_func(query):
    source = query[1]
    coef_list.append(query[1])
    intercept[0] += query[2]

    if len(coef_list) == 1:
        cent_list.append(source)
        median[0] = cent_list[0]
        return
    if cent_list == []:
        if median[0] > source:
            heapq.heappush(left_list, -source)
            left_sum[0] += source #
            tmp = -heapq.heappop(left_list)
            left_sum[0] -= 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[0] += source - tmp
            cent_list.append(tmp)
        median[0] = cent_list[0]
    else:
        if cent_list[0] < source:
            heapq.heappush(left_list, -cent_list[0])
            count[0] += 1
            left_sum[0] += cent_list[0]
            median[0] = cent_list[0]
            heapq.heappush(right_list, source)
            count[1] += 1
            right_sum[0] += source
            cent_list.remove(cent_list[0])
        else:
            heapq.heappush(left_list, -source)
            left_sum[0] += source
            count[0] += 1
            median[0] = source
            heapq.heappush(right_list, cent_list[0])
            count[1] += 1
            right_sum[0] += cent_list[0]
            cent_list.remove(cent_list[0])
    return
def solve_func():
    cent = 0
    if cent_list != []:
        cent = cent_list[0]
    minval = np.abs(left_sum[0]-count[0]*median[0]) + np.abs(right_sum[0]-count[1]*median[0]) + cent - len(cent_list)*median[0]
    minval += intercept[0]
    print(str(median[0]) + " " + str(minval))

for query in Qlist:
    if query[0] == 1:
        update_func(query)
    else:
        solve_func()

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
Q = int(input())
Qlist = [list(map(int,input().split())) for i in range(Q)]
#print(Qlist)
coef_list = []
intercept = [0]
# coef_listのうちmedianより小さい、同じ、大きい要素の数
left_list = []
cent_list = []
right_list = []
left_sum = 0
right_sum = 0

median = [0]
count = [0]

def update_func(query):
    count[0] += 1
    source = query[1]
    coef_list.append(query[1])
    intercept[0] += query[2]

    if len(coef_list) == 1:
        cent_list.append(source)
        median[0] = cent_list[0]
        return
    if cent_list == []:
        if median[0] > source:
            left_list.append(-source)
            tmp = -heapq.heappop(left_list)
            cent_list.append(tmp)
        elif right_list[0] > source:
            cent_list.append(source)
        else:
            right_list.append(source)
            tmp = heapq.heappop(right_list)
            cent_list.append(tmp)
        median[0] = cent_list[0]
    else:
        if cent_list[0] < source:
            heapq.heappush(left_list, -cent_list[0])
            median[0] = cent_list[0]
            heapq.heappush(right_list, source)
            cent_list.remove(cent_list[0])
        else:
            heapq.heappush(left_list, -source)
            median[0] = source
            heapq.heappush(right_list, cent_list[0])
            cent_list.remove(cent_list[0])

def solve_func():
    minval = sum(right_list) - sum(left_list) + sum(cent_list) - median[0]*count[0]

    minval += intercept[0]
    print(str(median[0]) + " " + str(minval))

for query in Qlist:
    if query[0] == 1:
        update_func(query)
    else:
        solve_func()

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
Qlist = [list(map(int,input().split())) for i in range(Q)]
coef_list = []
intercept = [0]

def update_func(query):
    coef_list.append(query[1])
    intercept[0] += (query[2])

def solve_func():
    idx = len(coef_list)//2
    med = coef_list[idx]
    minval = 0
    for i in range(len(coef_list)):
        minval += np.abs(med-coef_list[i])
    minval += intercept[0]
    print(str(med) + " " + str(minval))

for query in Qlist:
    if query[0] == 1:
        update_func(query)
    else:
        solve_func()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = 10**10

Q = int(input())
small, big = [INF], [INF]
l, r = 0, 0
B = 0
for i in range(Q):
    query = [int(x) for x in input().split()]
    if query[0] == 1:
        B += query[2]
        if len(small) <= len(big):
            if big[0] < query[1]:
                heappush(small, -big[0])
                l += -big[0]
                r -= big[0]
                heapreplace(big, query[1])
                r += query[1]
            else:
                heappush(small, -query[1])
                l += -query[1]
        else:
            if query[1] < -small[0]:
                heappush(big, -small[0])
                r += -small[0]
                l -= small[0]
                heapreplace(small, -query[1])
                l += -query[1]
            else:
                heappush(big, query[1])
                r += query[1]
    else:
        m1, m2 = -small[0], big[0]
        print(m1, l+r+m1*(len(small)-1)-m2*(len(big)-1)+B+(len(small)==len(big))*(m2-m1)*(len(small)-1))

Submission status: Wrong Answer

Solution code:
import bisect
def update(a,b):
    ind = bisect.bisect_right(A,a)
    if ind==len(A):
        memo[a] = memo[A[ind-1]]+a-A[ind-1]+b
    elif ind==0:
        memo[a] = memo[A[ind]]+A[ind]-a+b
    else:
        memo[a] = memo[A[ind-1]]+(memo[A[ind]]-memo[A[ind-1]])*(a-A[ind-1])//(A[ind]-A[ind-1])+b
    if ind!=0 and A[ind-1]!=a:
        for x in A:
            memo[x] += abs(x-a)+b
memo = {}
Q = int(input())
A = []
q,a,b = map(int,input().split())
memo[a] = b
A.append(a)
for i in range(1,Q):
    qry = input().split()
    if int(qry[0])==1:
        a = int(qry[1])
        b = int(qry[2])
        update(a,b)
        bisect.insort_right(A,a)
    else:
        if len(A)%2==0:
            a = A[(len(A)-1)//2]
            print(a,memo[a])
        else:
            a = A[len(A)//2]
            print(a,memo[a])

Submission status: Wrong Answer

Solution code:
import heapq
Q = int(input())
L = []
R = []
heapq.heapify(L)
heapq.heapify(R)
B = 0
n = 0
res = 0
for _ in range(1, Q + 1):
  q = input()
  if q == "2":
    print(-heapq.nlargest(1, L).pop(), 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))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
Q = int(input())
A = []
B = 0
for _ in range(1, Q + 1):
  q = input()
  res = 0
  if q == "2":
    if len(A) % 2 == 0:
      print(A[len(A) // 2 - 1], res + B)
    else:
      print(A[len(A) // 2 - 1], res + B)
  else:
    t, a, b = map(int, q.split())
    ind = bl(A, a)
    A.insert(ind, a)
    B += b
    for i in range(len(A)):
      res += abs(A[i] - A[len(A) // 2])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
Q = int(input())
A = []
B = 0
for _ in range(1, Q + 1):
  q = input()
  if q == "2":
    res = 0
    for i in range(len(A)):
      res += abs(A[i] - A[len(A) // 2])
    if len(A) % 2 == 0:
      print((A[len(A) // 2] + A[len(A) // 2 - 1]) // 2, res + B)
    else:
      print(A[len(A) // 2 - 1], res + B)
  else:
    t, a, b = map(int, q.split())
    ind = bl(A, a)
    A.insert(ind, a)
    B += b

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left,bisect
    import sys
    input = sys.stdin.readline
    
    Q = int(input())
    S = [list(map(int, input().split())) for i in range(Q)]
    
    left = 0
    right = 0
    b = 0
    A = []
    answer = []
    b += S[0][2]
    A.append(S[0][1])
    
    for i in range(1,Q):
        if S[i][0] == 2:
            if len(A)%2 == 0:
                x = A[len(A)//2 - 1]
                y = right - left - x + b
                answer.append([x,y])
            else:
                x = A[len(A)//2]
                y = right - left + b
                answer.append([x,y])
        else:
            a = S[i][1]
            b += S[i][2]
            if len(A)%2 == 0:
                j = bisect_left(A,a)
                if len(A)//2 - 1 >= j:
                    left += a
                    A.insert(j,a)
                elif j == len(A)//2:
                    left += A[len(A)//2 - 1]
                    A.insert(j,a)
                else:
                    left += A[len(A)//2 - 1]
                    right = right - A[len(A)//2] + a
                    A.insert(j,a)
            else:
                j = bisect(A,a)
                if len(A)//2 < j:
                    right += a
                    A.insert(j,a)
                elif len(A)//2 == j:
                    right += A[len(A)//2]
                    A.insert(j,a)
                else:
                    right += A[len(A)//2]
                    left = left - A[len(A)//2-1] + a
    for i in range(len(answer)):
        print(*answer[i])
            

main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left,bisect
    import sys
    input = sys.stdin.readline
    
    Q = int(input())
    S = [list(map(int, input().split())) for i in range(Q)]
    
    left = 0
    right = 0
    b = 0
    A = []
    answer = []
    b += S[0][2]
    A.append(S[0][1])
    
    for i in range(1,Q):
        if S[i][0] == 2:
            if len(A)%2 == 0:
                x = A[len(A)//2 - 1]
                y = right - left - x + b
                answer.append([x,y])
            else:
                x = A[len(A)//2]
                y = right - left + b
                answer.append([x,y])
        else:
            a = S[i][1]
            b += S[i][2]
            if len(A)%2 == 0:
                j = bisect_left(A,a)
                if len(A)//2 - 1 >= j:
                    left += a
                    A.insert(j,a)
                elif j == len(A)//2:
                    left += A[len(A)//2 - 1]
                    A.insert(j,a)
                else:
                    left += A[len(A)//2 - 1]
                    right = right - A[len(A)//2] + a
                    A.insert(j,a)
            else:
                j = bisect(A,a)
                if len(A)//2 < j:
                    right += a
                    A.insert(j,a)
                elif len(A)//2 == j:
                    right += A[len(A)//2]
                    A.insert(j,a)
                else:
                    right += A[len(A)//2]
                    left = left - A[len(A)//2-1] + a
    print(answer)
            

main()

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

Q = int(input())
#Q = 100000
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))
	#q.append([1, (i*17) % 10000, i])

a_list = []
a_list2 = []
b_sum = 0
a_sum = 0
a_sum_half = 0
length = 0
for i in range(Q):
	if len(q[i]) == 3:
		if len(a_list2) == 0:
			D = True
		else:
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list2,x)
			D = (x <= q[i][1])
		length += 1
		if length % 2 == 0 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, -q[i][1])
		elif length % 2 == 0 and D:
			heapq.heappush(a_list2, q[i][1])
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list, -x)
			a_sum_half += x
		elif length % 2 == 1 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, -q[i][1])
			x = heapq.heappop(a_list)
			a_sum_half += x
			heapq.heappush(a_list2, -x)
		else:
			heapq.heappush(a_list2, q[i][1])
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		if length % 2 == 0:
			argmin_x = -heapq.heappop(a_list)
			heapq.heappush(a_list, -argmin_x)
		else:
			argmin_x = heapq.heappop(a_list2)
			heapq.heappush(a_list2, argmin_x)
		print(a_list, a_list2, argmin_x, a_sum, a_sum_half)
		min_x = argmin_x*(length//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(length - length//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

Q = int(input())
#Q = 100000
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))
	#q.append([1, (i*17) % 10000, i])

a_list = []
a_list2 = []
b_sum = 0
a_sum = 0
a_sum_half = 0
length = 0
for i in range(Q):
	if len(q[i]) == 3:
		if len(a_list2) == 0:
			D = True
		else:
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list2,x)
			D = (x <= q[i][1])
		length += 1
		if length % 2 == 0 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, -q[i][1])
		elif length % 2 == 0 and D:
			heapq.heappush(a_list2, q[i][1])
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list, -x)
			a_sum_half += x
		elif length % 2 == 1 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, q[i][1])
			x = heapq.heappop(a_list)
			a_sum_half += x
			heapq.heappush(a_list2, -x)
		else:
			heapq.heappush(a_list2, q[i][1])
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		if length % 2 == 0:
			argmin_x = -heapq.heappop(a_list)
			heapq.heappush(a_list, -argmin_x)
		else:
			argmin_x = heapq.heappop(a_list2)
			heapq.heappush(a_list2, argmin_x)
		min_x = argmin_x*(length//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(length - length//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

Q = int(input())
#Q = 100000
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))
	#q.append([1, (i*17) % 10000, i])

a_list = []
a_list2 = []
b_sum = 0
a_sum = 0
a_sum_half = 0
length = 0
for i in range(Q):
	if len(q[i]) == 3:
		if len(a_list2) == 0:
			D = True
		else:
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list2,x)
			D = (x <= q[i][1])
		length += 1
		if length % 2 == 0 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, -q[i][1])
		elif length % 2 == 0 and D:
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list, -x)
			a_sum_half += x
		elif length % 2 == 1 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, q[i][1])
			x = heapq.heappop(a_list)
			a_sum_half += x
			heapq.heappush(a_list2, -x)
		else:
			heapq.heappush(a_list2, q[i][1])
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		if length % 2 == 0:
			argmin_x = -heapq.heappop(a_list)
			heapq.heappush(a_list, -argmin_x)
		else:
			argmin_x = heapq.heappop(a_list2)
			heapq.heappush(a_list2, argmin_x)
		min_x = argmin_x*(length//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(length - length//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math

Q = int(input())
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))

a_list = []
b_sum = 0
a_sum = 0
a_sum_half = 0
for i in range(Q):
	if len(q[i]) == 3:
		bisect.insort(a_list, q[i][1])
		a_sum += q[i][1]
		if len(a_list) % 2 == 0:
			a_sum_half += a_list[len(a_list)//2 - 1]
		b_sum += q[i][2]
	else:
		index = (len(a_list) - 1)//2
		argmin_x = a_list[index]
		min_x = argmin_x*(len(a_list)//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(len(a_list) - len(a_list)//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

Submission status: Wrong Answer

Solution code:
import heapq
q=int(input())
large=[]
small=[]
l_s=0
s_s=0
c=0
for i in range(q):
    s=input()
    if s[0]=='1':
        _,a,b=map(int,s.split())
        c+=b
        if large==[] and small==[]:
            heapq.heappush(small, -1*a)
            s_s+=a
        elif a> small[0]*-1:
            heapq.heappush(large, a)
            l_s-=a
        else:
            x=heapq.heappop(small)
            heapq.heappush(small, -1*a)
            heapq.heappush(large, -1*x)
        #print(large,small)
    else:
        print(small[0]*-1,c+s_s+l_s+small[0])

Submission status: Wrong Answer

Solution code:
def init(As):
    numPow2 = 2 ** (len(As)-1).bit_length()
    data = [0] * (numPow2+1)
    return data, numPow2
def updateRange(iA, A):
    iA += 1
    while iA > 0:
        data[iA] += A
        iA -= iA & -iA
def getValue(iA):
    iA += 1
    ans = 0
    while iA <= numPow2:
        ans += data[iA]
        iA += iA & -iA
    return ans

Q = int(input())
querys = []
As = []
for _ in range(Q):
    ss = input()
    if ss[0] == '1':
        t, A, B = map(int, ss.split())
        querys.append((1, A, B))
        As.append(A)
    else:
        querys.append((2, 0, 0))

As.sort()
convs = dict([(A, odr) for odr, A in enumerate(As)])

N = len(As)+1
data, numPow2 = init([0]*(N+1))

def binS(isOK):
    ng, ok = -1, N
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    return ok

anss = []
accB = 0
acc1 = 0
for t, A, B in querys:
    if t == 1:
        updateRange(convs[A], 1)
        accB += B
        acc1 += 1
    else:
        iA0 = binS(lambda mid: acc1 >= 2*getValue(mid))
        iA1 = binS(lambda mid: acc1 > 2*getValue(mid))
        anss.append((As[iA0-1], accB+As[iA1-1]-As[iA0-1]))

print('\n'.join(map(lambda x: str(x[0])+' '+str(x[1]), anss)))

Submission status: Wrong Answer

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 heappush, heappop


class QueryProcessor(object):
    def __init__(self):
        self.first = []
        self.latter = []
        self.fir_sum = 0
        self.lat_sum = 0
        self.b_sum = 0

    def process_query(self, q):
        query = q.split()
        if int(query[0]) == 1:
            a, b = map(int, query[1:3])
            self.update(a, b)

        else:
            print(-self.first[0], self.find())

    def update(self, a: int, b: int):
        # append new element to first or latter
        if len(self.first) == len(self.latter) == 0:
            heappush(self.first, -a)
            self.fir_sum += a

        elif len(self.first) == len(self.latter):
            if a <= -self.first[0]:
                heappush(self.first, -a)
                self.fir_sum += a

            else:
                tmp = heappop(self.latter)
                heappush(self.first, -tmp)
                heappush(self.latter, a)
                self.fir_sum += tmp
                self.lat_sum += (a-tmp)

        elif len(self.first) - len(self.latter) == 1:
            if a <= -self.first[0]:
                tmp = -heappop(self.first)
                heappush(self.first, -a)
                heappush(self.latter, tmp)
                self.fir_sum += (a-tmp)
                self.lat_sum += tmp

            else:
                heappush(self.latter, a)
                self.lat_sum += a

        # modify sum of first, latter and b
        self.b_sum += b

    def find(self):
        center = -self.first[0]
        return center * len(self.first) - self.fir_sum \
                + self.lat_sum - center * len(self.latter) \
                + self.b_sum


queryp = QueryProcessor()
q = ni()
for _ in range(q):
    query = ns()
    queryp.process_query(query)