solution of this problem in C language

include

include

int cmpfunc(const void *a, const void b) { return ((int*)a - (int)b); }

int lower_bound(int *arr, int n, int val) { int l = 0, r = n; while (l < r) { int mid = (l + r) / 2; if (arr[mid] < val) l = mid + 1; else r = mid; } return l; }

void printMedian(int *arr, int n) { if (n == 0) { printf("Wrong!\n"); return; } if (n % 2 == 1) { printf("%d\n", arr[n/2]); } else { long long sum = (long long)arr[n/2 - 1] + (long long)arr[n/2]; if (sum % 2 == 0) printf("%lld\n", sum/2); else printf("%.1f\n", sum/2.0); } }

void median(int N, char (*s)[3], int *x) { int *arr = malloc(N * sizeof(int)); int size = 0;

for (int i = 0; i < N; i++) {
    if (s[i][0] == 'a') {
        int pos = lower_bound(arr, size, x[i]);
        for (int j = size; j > pos; j--) arr[j] = arr[j-1];
        arr[pos] = x[i];
        size++;
        printMedian(arr, size);

    } else { 
        if (size == 0) {
            printf("Wrong!\n");
            continue;
        }
        int pos = lower_bound(arr, size, x[i]);
        if (pos == size || arr[pos] != x[i]) {
            printf("Wrong!\n");
            continue;
        }
        for (int j = pos; j < size-1; j++) arr[j] = arr[j+1];
        size--;
        printMedian(arr, size);
    }
}
free(arr);

}

int main() { int N; scanf("%d", &N); char s[N][3]; int x[N]; for (int i = 0; i < N; i++) { scanf("%s %d", s[i], &x[i]); } median(N, s, x); return 0; }

For those that write the challenge in C#, there is no built-in .NET collection that: only stores keys, keeps them sorted, and allows duplicates.

The only way that I have managed to do it is implement my custom data structure.

static void Median(string[] a, int[] x)
{
    SortedBag<int> numberList = new SortedBag<int>();
    for (int i = 0; i < a.Length; i++)
    {
        var operation = a[i]; //"a" or "r"
        var operationNumber = x[i]; // integer

        if (operation == "r")
        {
            if (!numberList.Contains(operationNumber))
            {
                Console.WriteLine("Wrong!");
                continue;
            }
            else
            {
                if (numberList.Contains(operationNumber))
                numberList.Remove(operationNumber);
            }
        }
        else
        {
            numberList.Add(operationNumber);
        }
        if (numberList.Count == 0)
        {
            Console.WriteLine("Wrong!");
        }
        else if (numberList.Count % 2 == 0)
        {
            var indexToCalculate = (numberList.Count) / 2;
            decimal median = (decimal)(numberList[indexToCalculate - 1]
                + (decimal)numberList[indexToCalculate]) / 2;
            Console.WriteLine(median);
        }
        else
        {
            int indexToCalculate = 0;
            if (numberList.Count != 1)
            {
                indexToCalculate = (numberList.Count) / 2;
            }
            var median = numberList[indexToCalculate];
            Console.WriteLine(median);
        }
    }
}
public class SortedBag<T> where T : IComparable<T>
 {
     private readonly List<T> _items = new();

     public void Add(T item)
     {
         int index = _items.BinarySearch(item);
         if (index < 0) index = ~index;
         _items.Insert(index, item);
     }

     public bool Remove(T item)
     {
         int index = _items.BinarySearch(item);
         if (index < 0)
             return false;

         while (index > 0 && _items[index - 1].CompareTo(item) == 0)
             index--;

         _items.RemoveAt(index);
         return true;
     }

     public int Count => _items.Count;

     // Indexer support
     public T this[int index] => _items[index];

     public bool Contains(T item)
     {
         return _items.BinarySearch(item) >= 0;
     }
 }

`

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