Submission #5716256

---

Source Code Expand

from heapq import*

class median_tree(object):
    def __init__(self):
        self.lower_than_med=[]
        self.higher_than_med=[]
        self.count=0
        self.low=0
        self.high=0
        self.median=0
    def push(self,x):
        self.count=1-self.count
        if self.count:
            y=heappushpop(self.higher_than_med,x)
            heappush(self.lower_than_med,-y)
            self.low +=-y
            self.high+=x-y
        else:
            y=heappushpop(self.lower_than_med,-x)
            heappush(self.higher_than_med,-y)
            self.low -=x+y
            self.high-=y
        self.median=-self.lower_than_med[0]

from heapq import*
n=int(input())
m=median_tree()

B=0
for i in range(n):
    I=input()
    if I[0]=="1":
        a,b,c=map(int,I.split())
        B+=c
        m.push(b)
    else:
        print(m.median,m.count%2*m.median+B+m.low+m.high)

Submission Info

Judge Result