4.cpp

#include <iostream>
#include <vector>
using namespace std;

struct CNode {
    CNode(int k) :
        key(k), height(1), count(1),
        Left(NULL), Right(NULL)
    { 
    }

    int key;
    int height;
    int count;

    CNode* Left;
    CNode* Right;
};

int Height(CNode* node)
{
    return node ? node->height : 0;
}


int Count(CNode* node) {
    return node ? node->count : 0;
}


int BalanceFactor(CNode* node)
{
    return Height(node->Right) - Height(node->Left);
}

void FixHeight(CNode* node)
{
    int hl = Height(node->Left);
    int hr = Height(node->Right);
    node->height = (hl > hr ? hl : hr) + 1;

    int cl = Count(node->Left);
    int cr = Count(node->Right);
    node->count = cl + cr + 1;
}

CNode* RotateRight(CNode* node) // правый поворот вокруг node
{
    if (node == NULL)
        return NULL;

    CNode *temp = node->Left;
    node->Left = temp->Right;
    temp->Right = node;
    FixHeight(node);
    FixHeight(temp);
    return temp;
}

CNode* RotateLeft(CNode *node) // левый поворот вокруг node
{
    if (node == NULL)
        return NULL;

    CNode *temp = node->Right;
    node->Right = temp->Left;
    temp->Left = node;
    FixHeight(node);
    FixHeight(temp);
    return temp;
}

CNode* Balance(CNode *node)
{
    if (node == NULL)
        return NULL;

    FixHeight(node);

    if( BalanceFactor(node) > 1 )
    {
        if( BalanceFactor(node->Right) < 0 )
            node->Right = RotateRight(node->Right);
        return RotateLeft(node);
    }
    if( BalanceFactor(node) < -1 )
    {
        if( BalanceFactor(node->Left) > 0  )
            node->Left = RotateLeft(node->Left);
        return RotateRight(node);
    }
    return node;
}

CNode* Insert(CNode* root, int key)
{
    if( root == NULL ) 
        return new CNode(key);

    if( key < root->key )
        root->Left = Insert(root->Left,key);
    else
        root->Right = Insert(root->Right,key);
    return Balance(root);
}

CNode* FindMin(CNode* node)
{
    return node->Left ? FindMin(node->Left) : node;
}

CNode* RemoveMin(CNode* node)
{
    if( node->Left==0 )
        return node->Right;
    node->Left = RemoveMin(node->Left);
    return Balance(node);
}

CNode* Remove(CNode* node, int k)
{
    if( !node ) return 0;
    if( k < node->key )
        node->Left = Remove(node->Left,k);
    else if( k > node->key )
        node->Right = Remove(node->Right,k);	
    else //  k == node->key 
    {
        CNode* temp = node->Left;
        CNode* r = node->Right;
        delete node;
        if( !r ) return temp;
        CNode* min = FindMin(r);
        min->Right = RemoveMin(r);
        min->Left = temp;
        return Balance(min);
    }
    return Balance(node);
}

void DeleteTree(CNode* node)
{
    if (node == NULL) 
        return;
    DeleteTree(node->Left);
    DeleteTree(node->Right);
    delete node;
}


int GetElemAtK(CNode* root, int k) {
    if (k == Count(root->Left))
        return root->key;

    if (k <= Count(root->Left))
        return GetElemAtK(root->Left, k);

    return GetElemAtK(root->Right, k - Count(root->Left) - 1);
}


int main()
{
    int n;
    cin >> n;

    CNode *root = NULL;
    int A, k;

    for (int i = 0; i < n; ++i) {
        cin >> A >> k;
        if( A >= 0 )
            root = Insert(root, A);
        else
            root = Remove(root, -A);

        cout << GetElemAtK(root, k) << endl;
    }

    DeleteTree(root);

    return 0;
}