AVL_Tree

#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <fstream>

class AVL_Tree
{
public:
    AVL_Tree() : root(0){}
    ~AVL_Tree();

    bool Insert(int x);
    bool Delete(int x);
    int Find(int x)
    {
        Node* node = find(root, x);
        return node->key;
    }

private:
    struct Node
    {
        int key;
        int high;
        int size;
        Node* left;
        Node* right;
        Node* parent;

        Node(int key) : key(key), high(1), size(1), left(0), right(0), parent(0) {}
    };

    Node* root;
    void leftTurn(Node*& node);
    void rightTurn(Node*& node);

    int hi(Node*& node) const;
    int upd(Node*& node) const;
    void updateSize(Node*& node);
    void balanse(Node*& node);

    void deleteNode(Node*& node);

    Node* getNext(Node* node);
    void detach(Node* node);
    Node* find(Node* node, int key) const;
    Node* f(Node* node, int key) const;
};

int AVL_Tree::hi(Node*& node) const
{
    return((node == 0) ? 0 : node->high);
}

int AVL_Tree::upd(Node*& node) const
{
    return((node == 0) ? 0 : node->size);
}

void AVL_Tree::leftTurn(Node*& node)
{
    int fl = (node->parent == 0) ? 1 : 0;
    Node* a = node;
    Node* b = node->right;
    a->right = b->left;
    if (a->right != 0)
        a->right->parent = a;
    b->parent = a->parent;
    if (!fl)
    {
        if (a->parent->key > a->key)
            a->parent->left = b;
        else if (a->parent->key < a->key)
            a->parent->right = b;
    }
    b->left = a;
    a->parent = b;
    if (fl)
        root = b;
    updateSize(a);
}

void AVL_Tree::rightTurn(Node*& node)
{
    int fl = (node->parent == 0) ? 1 : 0;
    Node* a = node;
    Node* b = node->left;
    a->left = b->right;
    if (a->left != 0)
        a->left->parent = a;
    b->parent = a->parent;
    if (!fl)
    {
        if (a->parent->key > a->key)
            a->parent->left = b;
        else if (a->parent->key < a->key)
            a->parent->right = b;
    }
    b->right = a;
    a->parent = b;
    if (fl)
        root = b;
    updateSize(a);
}

void AVL_Tree::updateSize(Node*& node)
{
    node->high = std::max(hi(node->left), hi(node->right)) + 1;
    node->size = upd(node->left)+ upd(node->right) + 1;
    if (node->parent != 0)
        updateSize(node->parent);
}

void AVL_Tree::balanse(Node*& node)
{
    if (std::abs(hi(node->left) - hi(node->right)) <= 1)
    {
        if (node->right != 0)
            balanse(node->right);
        if (node->left != 0)
            balanse(node->left);
        return;
    }
    if (hi(node->left) - hi(node->right) < -1)
    {
        if (hi(node->right->left) <= hi(node->right->right))
        {
            leftTurn(node);
        }
        else
        {
            rightTurn(node->right);
            leftTurn(node);
        }
    }
    else
    {
        if (hi(node->left->right) <= hi(node->left->left))
        {
            rightTurn(node);
        }
        else
        {
            leftTurn(node->left);
            rightTurn(node);
        }
    }
    if (node->right != 0)
        balanse(node->right);
    if (node->left != 0)
        balanse(node->left);
}

AVL_Tree::~AVL_Tree()
{
    deleteNode(root);
    root = 0;
}

void AVL_Tree::deleteNode(Node*& node)
{
    if (node == 0)
        return;
    deleteNode(node->left);
    deleteNode(node->right);

    delete node;
}

bool AVL_Tree::Insert(int Key)
{
    if (!root)
    {
        root = new Node(Key);
        return true;
    }

    Node* cur_node = root;
    while (true)
    {
        if (cur_node->key > Key && cur_node->left != 0)
            cur_node = cur_node->left;
        else if (cur_node->key < Key && cur_node->right != 0)
            cur_node = cur_node->right;
        else if (cur_node->key == Key)
            return false;
        else
            break;
    }
    if (cur_node->key > Key)
    {
        cur_node->left = new Node(Key);
        cur_node->left->parent = cur_node;
    }
    else if (cur_node->key < Key)
    {
        cur_node->right = new Node(Key);
        cur_node->right->parent = cur_node;
    }
    updateSize(cur_node);
    balanse(root);
    return true;
}

AVL_Tree::Node* AVL_Tree::find(Node* node, int x) const
{
    if (node == 0)
        return 0;
    int a = (node->left == 0) ? 0 : node->left->size;
    if (a == x)
        return node;
    else if (a > x)
        find(node->left, x);
    else
        find(node->right, x - a - 1);
}

AVL_Tree::Node* AVL_Tree::f(Node* node, int Key) const
{
    if (node->key == Key)
        return node;
    return node->key > Key ? f(node->left, Key) : f(node->right, Key);
}

bool AVL_Tree::Delete(int Key)
{
    Node* to_del = f(root, Key);

    if (to_del == 0)
        return false;

    if (to_del->left == 0 || to_del->right == 0)
    {
        detach(to_del);
        delete to_del;
        balanse(root);
        return true;
    }

    Node* next = getNext(to_del);

    to_del->key = next->key;

    detach(next);

    delete next;
    balanse(root);
    return true;
}

AVL_Tree::Node* AVL_Tree::getNext(Node* node)
{
    Node* candidate = node->right;
    while (candidate->left != 0)
        candidate = candidate->left;
    return candidate;
}

void AVL_Tree::detach(Node* node)
{
    assert(node->left == 0 || node->right == 0);

    if (node->parent == 0)
        return;

    Node* child = node->left == 0 ? node->right : node->left;

    if (child != 0)
    {
        child->parent = node->parent;
    }

    node->parent->left == node
        ? node->parent->left = child
        : node->parent->right = child;

    Node* parent = node->parent;
    node->left = 0;
    node->right = 0;
    node->parent = 0;
    updateSize(parent);
}


int main()
{
    AVL_Tree T;
    int n = 0, num = 0, k = 0;
    //std::ifstream finp;
    //finp.open("input.txt");
    std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        std::cin >> num >> k;
        if (num > 0)
            T.Insert(num);
        else
        {
            num = -num;
            T.Delete(num);
        }
        std::cout << T.Find(k) << '\n';
    }
    //finp.close();
    return 0;
}