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:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def bsearch(mn, mx, func):
    #func(i)=True を満たす最大のi (mn<=i<mx)
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mn = (idx + mx)//2, idx
            continue
        idx, mx = (idx + mn)//2, idx
    return idx

import sys;input=sys.stdin.readline
Q, = map(int, input().split())
qs = []
c = 0
j = 0
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        c += 1
    else:
        a, b = int(q[1]), int(q[2])
        qs.append((a, b, c, j))
        c = 0
        j+=1
if c:
    qs.append((a, b, c, j))

m = j
qqs = sorted(qs, key=lambda x:x[0])
j2i = dict()
i2a = dict()
for i, (a, b, c, j) in enumerate(qqs):
    j2i[j] = i+1
    i2a[i+1] = a

m = len(j2i)
st = Bit(m)
st_sum = Bit(m)
asum=bsum=0
#print(i2a)
#print(j2i)
for a, b, c, i in qs:
    if c:
        j = bsearch(0, m+1, lambda x: st.sum(x)<ci)
#        print(st_sum.sum(j+1))
        for _ in range(c):
            if not i%2:
                print(i2a[j+1], -2*st_sum.sum(j+1)+asum+bsum)
            else:
                print(i2a[j+1], -st_sum.sum(j)+(asum-st_sum.sum(j+1))+bsum)
    asum += a
    bsum += b
    st.add(j2i[i], 1)
    st_sum.add(j2i[i], a)
    ci = -(-(i+1)//2)

Submission status: Accepted

Solution code:
from heapq import *
import sys;input=sys.stdin.readline
Q, = map(int, input().split())
qs = []
c = 0
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        c += 1
    else:
        a, b = int(q[1]), int(q[2])
        qs.append((a, b, c))
        c = 0
if c:
    qs.append((a, b, c))

R = [10**18]
L = [10**18]
ss = 0
for a, b, c in qs:
    xs = []
    if c:
        x = heappop(L)
        for _ in range(c):
            print(-x, ss)
        heappush(L, x)
    x = heappop(R)
    y = -heappop(L)
    if x < a:
        heappush(R, a)
        heappush(R, a)
        heappush(L, -x)
        heappush(L, -y)
        ss += a-x
    elif y > a:
        heappush(L, -a)
        heappush(L, -a)
        heappush(R, x)
        heappush(R, y)
        ss += y-a
    else:
        heappush(L, -a)
        heappush(R, a)
        heappush(L, -y)
        heappush(R, x)
    ss += b

Submission status: Accepted

Solution code:
from heapq import *
Q, = map(int, input().split())
qs = []
c = 0
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        c += 1
    else:
        a, b = int(q[1]), int(q[2])
        qs.append((a, b, c, i))
        c = 0
if c:
    qs.append((a, b, c, i))

R = [10**18]
L = [10**18]
ss = 0
for a, b, c, i in qs:
    xs = []
    if c:
        x = heappop(L)
        for _ in range(c):
            print(-x, ss)
        heappush(L, x)
    x = heappop(R)
    y = -heappop(L)
    if x < a:
        heappush(R, a)
        heappush(R, a)
        heappush(L, -x)
        heappush(L, -y)
        ss += a-x
    elif y > a:
        heappush(L, -a)
        heappush(L, -a)
        heappush(R, x)
        heappush(R, y)
        ss += y-a
    else:
        heappush(L, -a)
        heappush(R, a)
        heappush(L, -y)
        heappush(R, x)
    ss += b

Submission status: Accepted

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]) == 0:
        L[0].append(-a)
        L[1].append(a)
    else:
        r0 = -1 * L[0][0]
        r1 = L[1][0]
        if a < r0:
            M[1] += r0 - a
        elif r1 < a:
            M[1] += a - r1

        if -1 * L[0][0] >= a:
            heapq.heappush(L[0], -a)
            t = -1 * heapq.heappushpop(L[0], -a)
            heapq.heappush(L[1], t)
        elif L[1][0] < a:
            heapq.heappush(L[1], a)
            t = heapq.heappushpop(L[1], a)
            heapq.heappush(L[0], -t)
        else:
            heapq.heappush(L[0], -a)
            heapq.heappush(L[1], a)
    # print(L, M)


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


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

    L = [[], []]
    M = [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: Accepted

Solution code:
import heapq

q = int(input())
l = []
r = []
lsum = 0
rsum = 0
cnt = 0
b = 0
#heapq正負注意
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==0:
            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 -= ax
            heapq.heappush(r,ax)
            rsum += ax
        cnt += 1

    else:
        x = -heapq.heappop(l)
        print(x, b + rsum - lsum + (len(l)+1-len(r))*x)
        heapq.heappush(l,-x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

def compress(l):
    l = list(set(l))
    l.sort()
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    
    for i in range(len(l)):
        d1[l[i]] = i
        d2[i] = l[i]
    
    return d1, d2

class BIT:#0-indexed
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def acc(self, i):#a0+...+ai
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s
    
    def add(self, i, x):#ai += x
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

def binary_search(c):
    l, r = 0, L-1
    
    while l<=r:
        m = (l+r)//2
        
        if bit.acc(m)>=(c+1)//2:
            r = m-1
        else:
            l = m+1
    
    return l
    
Q = int(input())
que = []
l = []

for _ in range(Q):
    que_i = tuple(map(int, input().split()))
    
    if len(que_i)==3:
        l.append(que_i[1])
    
    que.append(que_i)

d1, d2 = compress(l)
L = len(list(d1.keys()))
bit = BIT(L)
bit2 = BIT(L)
cnt = 0
b_acc = 0

for que_i in que:
    if len(que_i)==3:
        a, b = que_i[1], que_i[2]
        bit.add(d1[a], 1)
        bit2.add(d1[a], a)
        b_acc += b
        cnt += 1
    else:
        med_idx = binary_search(cnt)
        med = d2[med_idx]
        s = bit.acc(med_idx)*med-bit2.acc(med_idx)+(bit2.acc(L-1)-bit2.acc(med_idx))-(bit.acc(L-1)-bit.acc(med_idx))*med
        s += b_acc
        print(med, s)

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

    def lower_bound(self, w):
        if w<=0:
            return 0
        i = 0
        k = 1<<(self.n.bit_length())
        while k:
            if i+k <= self.n and self.data[i+k] < w:
                w -= self.data[i+k]
                i += k
            k >>= 1
        return i

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

a_set = sorted(set(i[1] for i in query if len(i)>1))
n = len(a_set)
dd = {j:i+1 for i,j in enumerate(a_set)}

cnt_bit = Binary_Indexed_Tree(n+2)
sum_bit = Binary_Indexed_Tree(n+2)

offset = 0
cnt = 0
for i in query:
    if len(i) == 1:
        left = cnt//2 + cnt%2
        right = cnt-left
        j = cnt_bit.lower_bound(left)
        x = a_set[j-1]
        ans = offset
        left_cnt = cnt_bit.sum_range(0,j-1)
        ans -= sum_bit.sum_range(0, j-1)
        ans += left_cnt*x
        right_cnt = cnt_bit.sum_range(j+1, n+1)
        ans += sum_bit.sum_range(j+1, n+1)
        ans -= right_cnt*x
        print(x, ans)
    else:
        _, a, b = i
        cnt_bit.add(dd[a], 1)
        sum_bit.add(dd[a], a)
        offset += b
        cnt += 1

Submission status: Accepted

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):
    sorted_A = sorted(set(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]
        val = query[i][1]
        num += 1
        p = comp[val]
        bit1.add(p+1,1)
        bit2.add(p+1,val)
    else:
        med = bit1.search((num+1)//2)
        sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
        minus_num = (bit1.sum(n)-bit1.sum(med)) - bit1.sum(med-1)
        print(values[med-1],sum_+cumb-minus_num*values[med-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    from heapq import heappop, heappush, heappushpop
    input = sys.stdin.readline

    Q = int(input())
    R = [10**9+1]
    L = [10**9+1]
    Rsum = 0
    Lsum = 0
    NL = 0
    NR = 0
    B = 0
    for _ in range(Q):
        query = input().rstrip('\n')
        if query == '2':
            Lmax = -L[0]
            print(Lmax, Lmax * NL - Lsum + Rsum - Lmax * NR + B)
        else:
            _, a, b = query.split()
            a = int(a)
            b = int(b)
            B += b
            if NL != NR:
                Lmax = -L[0]
                Rmin = R[0]
                if a >= Lmax:
                    heappush(R, a)
                    Rsum += a
                    NR += 1
                else:
                    newR = -heappushpop(L, -a)
                    heappush(R, newR)
                    Rsum += newR
                    Lsum += a - newR
                    NR += 1
                    Lmax = -L[0]
            else:
                Rmin = R[0]
                if a <= Rmin:
                    heappush(L, -a)
                    Lsum += a
                    NL += 1
                else:
                    newL = heappushpop(R, a)
                    heappush(L, -newL)
                    Lsum += newL
                    Rsum += a - newL
                    NL += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

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

l = -10**9-1
r = 10**9 + 1
ll = []
rl = []
ls = l
rs = r
bs = 0
ans = 0
Q = int(input())
for i in range(Q):
    t = input()
    if t == "2\n":
        print("{} {}".format(l, -((ls-rs+2*10**9+2)//2)+bs))
    else:
        _, a, b = (int(i) for i in t.split())
        bs += b
        if a < l:
            heapq.heappush(rl, r)
            ls -= l
            rs += l
            r = l
            heapq.heappush(ll, -a)
            heapq.heappush(ll, -a)
            ls += 2*a
            l = -heapq.heappop(ll)
        elif a > r:
            heapq.heappush(ll, -l)
            rs -= r
            ls += r
            l = r
            heapq.heappush(rl, a)
            heapq.heappush(rl, a)
            rs += 2*a
            r = heapq.heappop(rl)
        else:
            heapq.heappush(ll, -l)
            heapq.heappush(rl, r)
            ls += a
            rs += a
            l = a
            r = a

Submission status: Accepted

Solution code:
import heapq

Q = int(input())
m = L = R = 0
l, r = [], []
n = 0
b = 0

for i in range(Q):
  query = list(map(int, input().split()))
  if len(query) == 3: # 更新クエリ
    b += query[2]
    new = query[1]
    if  n == 0:
      m = new
    elif n == 1:
      if new <= m:
        heapq.heappush(l, -new)
        heapq.heappush(r, m)
        L, R = new, m
        m = new
      else:
        heapq.heappush(l, -m)
        heapq.heappush(r, new)
        L, R = m, new
    elif n == 2:
      if new < m:
        m = -heapq.heappop(l)
        heapq.heappush(l, -new)
        L = new
      else:
        _r = heapq.heappop(r)
        if new < _r:
          m = new
          heapq.heappush(r, _r)
        else:
          m = _r
          heapq.heappush(r, new)
          R = new
    else:
      _l = - l[0]
      _r = r[0]
      if n%2:
        if new <= _l:
          _ = heapq.heappop(l)
          heapq.heappush(l, -new)
          heapq.heappush(r, m)
          m, L, R = _l, L+new, R+m
        elif new <= m:
          heapq.heappush(r, m)
          m, L, R = new, L+new, R+m
        else:
          heapq.heappush(r, new)
          L, R = L+m, R+new
      else:
        if new <= m:
          heapq.heappush(l, -new)
          L += new - m
        elif new <= _r:
          heapq.heappush(l, -m)
          m = new
        else:
          _ = heapq.heappop(r)
          heapq.heappush(l, -m)
          heapq.heappush(r, new)
          m, R = _r, R+new-_r
    n += 1
  else: # 求値クエリ
    print(m, R-L+b)

Submission status: Accepted

Solution code:
from heapq import *
l = list()
r = list()
q = int(input())
sb = 0
sr = 0
sl = 0
f = 0
for _ in range(q):
  t = list(map(int, input().split()))
  if t[0] == 1:
    f ^= 1
    _, a, b = t
    sb += b
    if f:
      c = heappushpop(r, a)
      sr += a - c
      heappush(l, -c)
      sl += c
    else:
      c = -heappushpop(l, -a)
      sl += a - c
      heappush(r, c)
      sr += c   
  else:
    print(-l[0], l[0]*(len(r)-len(l)) + sr - sl + sb)

Submission status: Accepted

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)

            if nx < ox:
            
                fx += (ox-nx) * ( len(Rheap) - len(Lheap))

            elif nx > ox:

                fx += (nx-ox) * ( len(Lheap) - 1 - (len(Rheap) + 1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

Q = INT()
_, a, b = MAP()
mid = a
asm = 0
bsm = b
ln = 1
que1, que2 = [-a], [INF]
for _ in range(Q-1):
    li = LIST()
    if li[0] == 1:
        a, b = li[1:]
        bsm += b
        l = -que1[0]
        r = que2[0]
        if ln % 2 == 1:
            asm += abs(a - l)
            if a < mid:
                heappush(que1, -a)
                heappush(que2, -que1[0])
                heappop(que1)
            else:
                heappush(que2, a)
        else:
            if a < l:
                asm += abs(a - l)
            elif a > r:
                asm += abs(a - r)
            if a > mid:
                heappush(que2, a)
                heappush(que1, -que2[0])
                heappop(que2)
            else:
                heappush(que1, -a)
        ln += 1
        mid = -que1[0]
    else:
        print(mid, asm + bsm)

Submission status: Accepted

Solution code:
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]
import heapq

L = []
R = []
pop = heapq.heappop
push = heapq.heappush
A, B, C = 0, 0, 0

def nasu(a):
  global A
  global C
  if len(R) == 0:
    push(R, a)
    C = a
    return
  if len(L) == 0:
    r = pop(R)
    push(L, -min(a, r))
    push(R, max(a, r))
    A += abs(a - r)
    C = min(a, r)
    return
  if len(L) < len(R):
    r = pop(R)
    l = -pop(L)
    push(L, -l)
    push(L, -min(a, r))
    push(R, max(a, r))
    A += abs(a - r)
    if a < l:
      C = l
    elif a < r:
      C = a
    return
  l = -pop(L)
  r = pop(R)
  if l <= a and a <= r:
    push(L, -l)
    push(R, r)
    push(R, a)
    C = a
  elif a < l:
    push(L, -a)
    push(R, r)
    push(R, l)
    A += abs(a - l)
    C = l
  else:
    push(L, -l)
    push(R, a)
    push(R, r)
    A += abs(a - r)
    C = r

for q in Query:
  if q[0] == 1:
    nasu(q[1])
    B += q[2]
  if q[0] == 2:
    print(C, A + B)

Submission status: Accepted

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

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

INF = 10**18

Q = int(input())
count = 0
s = 0

upper = [INF]
lower = [INF]
heapq.heapify(upper)
heapq.heapify(lower)

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0]==1:
        count += 1
        s += q[2]
        a = q[1]
        u = heapq.heappop(upper)
        l = -heapq.heappop(lower)
        if count%2==0:
            if a<l:
                heapq.heappush(lower,-a)
                heapq.heappush(upper,l)
                heapq.heappush(upper,u)
                s += l-a
            else:
                heapq.heappush(lower,-l)
                heapq.heappush(upper,a)
                heapq.heappush(upper,u)
                s += a-l
        else:
            if a<=u:
                heapq.heappush(lower,-l)
                heapq.heappush(lower,-a)
                heapq.heappush(upper,u)
                s += max(0,l-a)
            else:
                heapq.heappush(lower,-l)
                heapq.heappush(lower,-u)
                heapq.heappush(upper,a)
                s += a-u

    else:
        x = -heapq.heappop(lower)
        print(x,s)
        heapq.heappush(lower,-x)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i,x,bit):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum(i,bit):
        res = 0
        while i :
            res += bit[i]
            i -= i&-i
        return res
    Q = I()
    q = LIR(Q)
    bit = [0]*(Q+1)
    bit2  = [0]*(Q+1)
    bit3 = [0]*(Q+1)
    bit4 = [0]*(Q+1)
    A = []
    for qi in q:
        if qi[0] == 1:
            a = qi[1]
            A.append(a)
    qa = [i for i in A]
    qa.sort()
    ia = {i:bisect.bisect_left(qa,i) for i in A}
    revqa = [-i for i in qa[::-1]]
    revia = {i:bisect.bisect_left(revqa,-i) for i in A}
    sb = 0
    n = 0
    for qi in q:
        if qi[0] == 1:
            a,b = qi[1:]
            ia[a] += 1
            revia[a] += 1
            i = ia[a]
            revi = revia[a]
            add(i,1,bit)
            add(i,a,bit2)
            add(revi,1,bit3)
            add(revi,a,bit4)
            sb += b
            n += 1
        else:
            l = 0
            r = Q
            k = (n-1)>>1
            while r-l > 1:
                m = (l+r) >> 1
                if sum(m,bit) <= k:
                    l = m
                else:
                    r = m
            fa = qa[l]
            i = ia[fa]
            revi = revia[fa]
            s1 = sum(l,bit)
            s2 = sum(l,bit2)
            s3 = sum(revi,bit3)
            s4 = sum(revi,bit4)
            s = fa*s1-s2+s4-fa*s3+sb
            print(fa,s)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

def main():
    q=int(input())
    res = 0

    x=list(map(int,input().split()))
    a=x[1]
    res += x[2]
    asmall = [a*-1]
    alarge = [a]
    heapq.heapify(asmall)
    heapq.heapify(alarge)

    r1 = a
    r2 = a

    for _ in range(q-1):
        x=list(map(int,input().split()))
        if x[0] ==1:
            a = x[1]
            res += x[2]
            if r1 <= a and a <= r2: pass
            else: res += min(abs(a-r1),abs(a-r2))
            mid1 = asmall[0] * -1
            if mid1 > a:
                heapq.heappush(alarge,heapq.heappop(asmall) * -1)
                heapq.heappush(asmall,-a)
                heapq.heappush(asmall,-a)
            else:
                mid2 = alarge[0]
                if mid2 >= a:
                    heapq.heappush(asmall,-a)
                    heapq.heappush(alarge,a)
                else:
                    heapq.heappush(asmall,heapq.heappop(alarge) * -1)
                    heapq.heappush(alarge,a)
                    heapq.heappush(alarge,a)
            r1 = asmall[0] * -1
            r2 = alarge[0]
        if x[0] == 2:
            print(str(r1)+" "+str(res))

main()

Submission status: Accepted

Solution code:
# f127_7では中央値を毎回抜き出しているせいで遅かったので改善
# heapの最小値は[0]で出せる

import heapq

n = int(input())

# 中央値より左・右の管理
l=[10**10]
r=[10**10]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0

ans = 0

for i in range(n):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if lenl>lenr:
            lenr+=1
            x = -l[0]
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(r,x)
                heapq.heapreplace(l,-q[1])
        else:
            lenl+=1
            x = r[0]
            if x<q[1]:
                heapq.heappush(l,-x)
                heapq.heapreplace(r,q[1])
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(-l[0]-q[1])
    if q[0]==2:
        print(-l[0], ans)

Submission status: Accepted

Solution code:
import heapq


n = int(input())
s = list(map(int, input().split()))

# 中央値より左・右の管理
l=[]
r=[]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0

# 中央値
x = s[1]

# b含めた答え
ans = s[2]

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if lenl>=lenr:
            lenr+=1
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(r,x)
                x = -heapq.heappushpop(l,-q[1])
        else:
            lenl+=1
            if x<q[1]:
                heapq.heappush(l,-x)
                x = heapq.heappushpop(r,q[1])
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(x-q[1])
    if q[0]==2:
        print(x, ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    n = int(input())
    s = list(map(int, input().split()))

    # 中央値より左・右の管理
    l=[]
    r=[]
    heapq.heapify(l)
    heapq.heapify(r)
    lenl=0
    lenr=0
    # 中央値
    x = s[1]

    # b含めた答え
    ans = s[2]

    for i in range(n-1):
        q = list(map(int,input().split()))
        if q[0]==1:
            ans += q[2]
            if (lenl+lenr)%2==0:
                lenr+=1
                ans+=abs(x-q[1])
                if x<=q[1]:
                    heapq.heappush(r,q[1])
                else:
                    heapq.heappush(l,-q[1])
                    heapq.heappush(r,x)
                    x = -heapq.heappop(l)
            else:
                lenl+=1
                if x<q[1]:
                    heapq.heappush(l,-x)
                    heapq.heappush(r,q[1])
                    x=heapq.heappop(r)
                else:
                    heapq.heappush(l,-q[1])
                ans+=abs(x-q[1])
        if q[0]==2:
            print(x, ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

n = int(input())
s = list(map(int, input().split()))

# 中央値より左・右の管理
l=[]
r=[]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0
# 中央値
x = s[1]

# b含めた答え
ans = s[2]

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if (lenl+lenr)%2==0:
            lenr+=1
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(l,-q[1])
                heapq.heappush(r,x)
                x = -heapq.heappop(l)
        else:
            lenl+=1
            if x<q[1]:
                heapq.heappush(l,-x)
                heapq.heappush(r,q[1])
                x=heapq.heappop(r)
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(x-q[1])
    if q[0]==2:
        print(x, ans)