`

class Node: def init(self, data): self.data = data self.left = None self.right = None self.height = 1 self.size = 1

class AVLTree: def init(self): self.root = None

def getMedian(self):
    if not self.root:
        return None

    if self.root.size % 2 == 0:
        m1 = self.root.size // 2
        m2 = m1 + 1
        median_value = (self.findNthElement(m1) + self.findNthElement(m2)) / 2
    else:
        median_value = self.findNthElement(self.root.size // 2 + 1)

    return self.formatNumber(median_value)

def findNthElement(self, n):
    node = self.root
    while node:
        left_size = self.getSize(node.left)
        if n <= left_size:
            node = node.left
        elif n == left_size + 1:
            return node.data
        else:
            n -= left_size + 1
            node = node.right
    return None

def formatNumber(self, num):
    if num == int(num):
        return str(int(num))
    return str(num).rstrip("0").rstrip(".")

def insert(self, data):
    self.root = self._insert(self.root, data)
    median_value = self.getMedian()
    if median_value is not None:
        print(median_value)
    else:
        print("Wrong!")

def _insert(self, node, data):
    if not node:
        return Node(data)

    if data < node.data:
        node.left = self._insert(node.left, data)
    else:
        node.right = self._insert(node.right, data)

    node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
    node.size = 1 + self.getSize(node.left) + self.getSize(node.right)

    return self._rebalance(node)

def delete(self, data):
    if not self.root:
        print("Wrong!")
        return

    initial_size = self.root.size
    self.root = self._delete(self.root, data)
    if self.root and self.root.size == initial_size:
        print("Wrong!")
    else:
        median_value = self.getMedian()
        if median_value is not None:
            print(median_value)
        else:
            print("Wrong!")

def _delete(self, node, data):
    if not node:
        return node

    if data < node.data:
        node.left = self._delete(node.left, data)
    elif data > node.data:
        node.right = self._delete(node.right, data)
    else:
        if not node.left:
            return node.right
        elif not node.right:
            return node.left

        inorder_successor = self.findInorderSuccessor(node)
        node.data = inorder_successor.data
        node.right = self._delete(node.right, inorder_successor.data)

    node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
    node.size = 1 + self.getSize(node.left) + self.getSize(node.right)

    return self._rebalance(node)

def findInorderSuccessor(self, node):
    current = node.right
    while current.left:
        current = current.left
    return current

def _rebalance(self, node):
    bf = self.getBalanceFactor(node)

    if bf > 1 and self.getBalanceFactor(node.left) >= 0:
        return self.rotateRight(node)

    if bf > 1 and self.getBalanceFactor(node.left) < 0:
        node.left = self.rotateLeft(node.left)
        return self.rotateRight(node)

    if bf < -1 and self.getBalanceFactor(node.right) <= 0:
        return self.rotateLeft(node)

    if bf < -1 and self.getBalanceFactor(node.right) > 0:
        node.right = self.rotateRight(node.right)
        return self.rotateLeft(node)

    return node

def getSize(self, node):
    return node.size if node else 0

def getHeight(self, node):
    return node.height if node else 0

def getBalanceFactor(self, node):
    if not node:
        return 0
    return self.getHeight(node.left) - self.getHeight(node.right)

def rotateRight(self, node):
    left = node.left
    left_right = left.right

    left.right = node
    node.left = left_right

    node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
    node.size = 1 + self.getSize(node.left) + self.getSize(node.right)
    left.height = 1 + max(self.getHeight(left.left), self.getHeight(left.right))
    left.size = 1 + self.getSize(left.left) + self.getSize(left.right)

    return left

def rotateLeft(self, node):
    right = node.right
    right_left = right.left

    right.left = node
    node.right = right_left

    node.height = 1 + max(self.getHeight(node.left), self.getHeight(node.right))
    node.size = 1 + self.getSize(node.left) + self.getSize(node.right)
    right.height = 1 + max(self.getHeight(right.left), self.getHeight(right.right))
    right.size = 1 + self.getSize(right.left) + self.getSize(right.right)

    return right

def inorder(self):
    node = self.root
    stack = []
    res = []
    while stack or node:
        while node:
            stack.append(node)
            node = node.left

        node = stack.pop()
        res.append(node.data)
        node = node.right

    print(res)

def median(s, x): avlTree = AVLTree() for op, val in zip(s, x): if op == "a": avlTree.insert(val) elif op == "r": avlTree.delete(val)

Done it with the AVL Tree. Every node of the tree tracks not only height but also size which allows to calculate the index of the node and therefore the median.

def print_median(tree):
    if not tree:
        print("Wrong!")
        return

    if tree.root.size % 2:
        m = tree[(tree.root.size // 2) + (tree.root.size % 2)]
        if m is None:
            print("Wrong!")
        else:
            print(m.value)
    else:
        m1 = tree[(tree.root.size // 2) + (tree.root.size % 2)]
        m2 = tree[(tree.root.size // 2) + (tree.root.size % 2) + 1]

        if not m1 and not m2:
            print("Wrong!")
        else:
            print(round((m1.value + m2.value) / 2, 1) if (m1.value + m2.value) % 2 else (m1.value + m2.value) // 2)


def median(a, x):
    tree = AVL()

    for e in zip(a, x):
        if e[0] == 'a':
            tree.insert_value(e[1])
            print_median(tree)
        elif e[0] == 'r':
            m = tree.search_value(e[1])
            if m is None:
                print("Wrong!")
            else:
                tree.delete_value(e[1])
                print_median(tree)

` class AVL: def init(self): self.root = None

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

def __getitem__(self, idx):

    if idx == 0:
        return self.min_node(self.root)

    if not self.root or idx > self.root.size or idx < 0:
        raise IndexError()

    tmp = self.root
    elms = 0
    while tmp and not (idx == (elms + self.len(tmp.left) + 1)):
        if idx < (elms + self.len(tmp.left) + 1):
            tmp = tmp.left
        elif idx > (elms + self.len(tmp.left) + 1):
            elms += (self.len(tmp.left) + 1)
            tmp = tmp.right
    else:
        return tmp

The rest of the AVL tree implementation you may find on geeksforgeeks.

i got this one

https://ideone.com/YWjB9B

Simple solution

import bisect
def median(a,x):
    ll=[]
    
    
    for (l,r) in zip(a,x):
        if l=='r':
            if r in ll:
                index=bisect.bisect(ll,r)
                ll.pop(index-1)
            else:
                print("Wrong!")
                continue
                
        else:
            bisect.insort(ll,r)
        if(len(ll)==0):
            print("Wrong!")
            continue
        median=(ll[len(ll)//2]+ll[(len(ll)-1)//2])/2
        x=str(median)
        x=x.rstrip('0')
        x=x.rstrip('.')
        print(x)

The multi-set solution is O(n) for add and O(n) for remove (thus no better than using a sorted linkedlist). This is a heap based solution that's O(log n) for add but still O(n) for remove.

from heapq import heappop, heappush, heapify

class MedianTracker:
    def __init__(self):
        self.left = []
        self.right = []

    def _shift_left(self):
        while len(self.right) > len(self.left) + 1:
            num = heappop(self.right)
            heappush(self.left, -num)

    def _shift_right(self):
        while len(self.left) > len(self.right) + 1:
            num = -heappop(self.left)
            heappush(self.right, num)

    def remove(self, num):
        if self.left and num <= -self.left[0]:
            self.left.remove(-num)
            heapify(self.left)
            self._shift_left()
        elif self.right and num >= self.right[0]:
            self.right.remove(num)
            heapify(self.right)
            self._shift_right()
        else:
            raise ValueError('removing element not in list')

    def add(self, num):
        if self.left and num > -self.left[0]:
            heappush(self.right, num)
            self._shift_left()
        else:
            heappush(self.left, -num)
            self._shift_right()

    def _median(self):
        if not self.left and not self.right:
            raise ValueError('no median when empty')
        if len(self.left) == len(self.right):
            return (-self.left[0] + self.right[0]) / 2
        if len(self.left) > len(self.right):
            return -self.left[0]
        return self.right[0]

    def median(self):
        med = self._median()
        if isinstance(med, float) and med.is_integer():
            return int(med)
        return med

#!/bin/python
def median(a,x):
    median_tracker = MedianTracker()
    for op, num in zip(a, x):
        if op == 'r':
            try:
                median_tracker.remove(num)
                print(median_tracker.median())
            except:
                print('Wrong!')
        elif op == 'a':
            median_tracker.add(num)
            print(median_tracker.median())

N = int(input())
s = []
x = []
for i in range(0, N):
   tmp = input().strip().split(' ')
   a, b = [xx for xx in tmp]
   s.append(a)
   x.append(int(b))
median(s,x)