Cod sursa(job #1714063)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 7 iunie 2016 12:11:05
Problema Secv8 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.66 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

class Treap
{
private:
    struct _treap
    {
        int key, priority, sz;
        _treap *lft, *rgt;

        _treap()
        {
            key = priority = sz = 0;
            lft = rgt = 0;
        }

        _treap(int _key, int _priority, int _sz, _treap *_lft, _treap *_rgt)
        {
            key = _key;
            priority = _priority;
            sz = _sz;
            lft = _lft;
            rgt = _rgt;
        }
    }*R, *nil;

    int getRandomPriority()
    {
        int mod = (1 << 30) - 1;
        int priority = (rand() & mod) + 1;
        return priority;
    }

    void Balance(_treap *&T)
    {
        if(T -> priority < T -> lft -> priority)
            leftRotate(T);
        if(T -> priority < T -> rgt -> priority)
            rightRotate(T);

        sizeUpdate(T -> lft);
        sizeUpdate(T -> rgt);
        sizeUpdate(T);
    }

    void leftRotate(_treap *&T)
    {
        _treap *_T = T -> lft;
        T -> lft = _T -> rgt;
        _T -> rgt = T;
        T = _T;
    }

    void rightRotate(_treap *&T)
    {
        _treap *_T = T -> rgt;
        T -> rgt = _T -> lft;
        _T -> lft = T;
        T = _T;
    }

    void sizeUpdate(_treap *&T)
    {
        if(T == nil)    return;
        T -> sz = T -> lft -> sz + T -> rgt -> sz + 1;
    }

    void Insert(_treap *&T, int pos, int key, int priority)
    {
        if(T == nil)
        {
            T = new _treap(key, priority, 1, nil, nil);
            return;
        }

        if(T -> lft -> sz >= pos)
            Insert(T -> lft, pos, key, priority);
        else
            Insert(T -> rgt, pos - (T -> lft -> sz) - 1, key, priority);

        Balance(T);
    }

    void Erase(_treap *&T, int pos)
    {
        if(T -> lft -> sz >= pos)
            Erase(T -> lft, pos);
        else if(T -> lft -> sz + 1 < pos)
            Erase(T -> rgt, pos - T -> lft -> sz - 1);
        else
        {
            if(T -> lft == nil && T -> rgt == nil)
            {
                delete T;
                T = nil;
            }
            else
            {
                if(T -> lft -> priority > T -> rgt -> priority)
                {
                    leftRotate(T);
                }
                else
                {
                    rightRotate(T);
                }
                Erase(T, pos);
            }
        }
    }

    int Access(_treap *&T, int pos)
    {
        if(T -> lft -> sz >= pos)
            return Access(T -> lft, pos);
        if(T -> lft -> sz + 1 == pos)
            return T -> key;
        return Access(T -> rgt, pos - T -> lft -> sz - 1);
    }

    void Split(_treap *&T, _treap *&lT, _treap *&rT, int pos)
    {
        Insert(T, pos - 1, 0, (1 << 30) + 5);
        lT = T -> lft;
        rT = T -> rgt;
        delete T;
        T = nil;
    }

    void Join(_treap *&T, _treap *&lT, _treap *&rT)
    {
        T = new _treap(0, 0, 1 + lT -> sz + rT -> sz, lT, rT);
        Erase(T, lT -> sz + 1);
    }

    void Print(_treap *&T)
    {
        if(T == nil)    return;
        Print(T -> lft);
        printf("%d ", T -> key);
        Print(T -> rgt);
    }

public:
    Treap()
    {
        nil = new _treap;
        nil -> lft = nil -> rgt = nil;
        R = nil;
    }

    ~Treap() {}

    void Insert(int pos, int val)
    {
        Insert(R, pos - 1, val, getRandomPriority());
    }

    int Access(int pos)
    {
        return Access(R, pos);
    }

    void Delete(int st, int dr)
    {
        _treap *lftT, *auxT, *delT, *rgtT;
        Split(R, lftT, auxT, st);
        Split(auxT, delT, rgtT, dr - st + 2);
        Join(R, lftT, rgtT);
    }

    void Print()
    {
        Print(R);
    }
};
Treap trp;

int main()
{
    #ifdef FILE_IO
    freopen("secv8.in", "r", stdin);
    freopen("secv8.out", "w", stdout);
    #endif

    int T, k;
    scanf("%d%d\n", &T, &k);
    assert(k == 0);
    while(T--)
    {
        char op;
        scanf("%c", &op);
        if(op == 'I')
        {
            int x, y;
            scanf("%d%d\n", &x, &y);
            trp.Insert(x, y);
        }
        else if(op == 'A')
        {
            int x;
            scanf("%d\n", &x);
            printf("%d\n", trp.Access(x));
        }
        else if(op == 'R')
        {
            int x, y;
            scanf("%d%d\n", &x, &y);
        }
        else if(op == 'D')
        {
            int x, y;
            scanf("%d%d\n", &x, &y);
            trp.Delete(x, y);
        }
    }
    trp.Print();

    return 0;
}