Cod sursa(job #1732588)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 21 iulie 2016 23:13:28
Problema Secv8 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 11.89 kb
#include <bits/stdc++.h>
using namespace std;

template< class TYPE >
class nrxPositionTreap {

private:

    int treapSize = 0;

    static const int CONST1  = 29;
    static const int CONST2  = 31;
    static const int MOD1    = 666013;
    static const int MOD2    = 666019;
    static const int MAXSIZE = 200005;

    vector< pair<int, int> > myHash;

    struct treapNode {
        TYPE key, minim, maxim, first, last; int nodeSize, priority;
        pair <int, int> nodeHash; bool reversed;

        treapNode *leftNode;
        treapNode *rightNode;

        treapNode() {
            this -> nodeSize = 0; this -> nodeHash = make_pair( 0, 0 ); this -> priority = INT_MIN; this -> reversed = false;
            this -> minim = this -> key; this -> maxim = this -> key; this -> first = this -> key; this -> last = this -> key;
            this -> leftNode = NULL;
            this -> rightNode = NULL;
        }

        treapNode( TYPE key, int nodeSize, int priority, pair <int, int> nodeHash, treapNode *leftNode, treapNode *rightNode ) {
            this -> key = key; this -> nodeSize = nodeSize; this -> priority = priority; this -> nodeHash = nodeHash;
            this -> minim = key; this -> maxim = key; this -> first = key; this -> last = key; this -> reversed = false;
            this -> leftNode = leftNode;
            this -> rightNode = rightNode;
        }
    } *root, *emptyNode;

    void updateSize( treapNode *&node ) {
        node -> nodeSize = 1 + node -> leftNode -> nodeSize + node -> rightNode -> nodeSize;
        return;
    }

    void updateHash( treapNode *&node ) {
        node -> nodeHash.first  = (int) ( ( node -> rightNode -> nodeHash.first +
                                            myHash[ node -> rightNode -> nodeSize + 1 ].first +
                                            node -> leftNode -> nodeHash.first  * 1LL * myHash[ node -> rightNode -> nodeSize + 2 ].first  ) % MOD1 );

        node -> nodeHash.second = (int) ( ( node -> rightNode -> nodeHash.second +
                                            myHash[ node -> rightNode -> nodeSize + 1 ].second +
                                            node -> leftNode -> nodeHash.second * 1LL * myHash[ node -> rightNode -> nodeSize + 2 ].second ) % MOD2 );
        return;
    }

    void updateMinMax( treapNode *&node ) {
        node -> minim = node -> key;
        if( node -> leftNode  != emptyNode ) node -> minim = min( node -> minim, node -> leftNode  -> minim );
        if( node -> rightNode != emptyNode ) node -> minim = min( node -> minim, node -> rightNode -> minim );

        node -> maxim = node -> key;
        if( node -> leftNode  != emptyNode ) node -> maxim = max( node -> maxim, node -> leftNode  -> maxim );
        if( node -> rightNode != emptyNode ) node -> maxim = max( node -> maxim, node -> rightNode -> maxim );

        return;
    }

    void updateFirstLast( treapNode *&node ) {
        node -> first = ( ( node -> leftNode == emptyNode )  ? node -> key : node -> leftNode -> first );
        node -> last  = ( ( node -> rightNode == emptyNode ) ? node -> key : node -> rightNode -> last );
        return;
    }

    void updateReverse( treapNode *&node ) {
        if( node -> reversed == true ) {
            swap( node -> leftNode, node -> rightNode ); node -> reversed = false;

            if( node -> leftNode  != emptyNode )
                node -> leftNode  -> reversed = !( node -> leftNode  -> reversed );

            if( node -> rightNode != emptyNode )
                node -> rightNode -> reversed = !( node -> rightNode -> reversed );
        }
    }

    void updateValues( treapNode *&node ) {
        updateReverse( node );
        updateSize( node );
        updateHash( node );
        updateMinMax( node );
        updateFirstLast( node );
    }

    void rotateLeft( treapNode *&node ) {
        updateValues( node );
        updateValues( node -> leftNode );
        treapNode *auxNode = node -> leftNode;

        node -> leftNode = auxNode -> rightNode;
        auxNode -> rightNode = node; node = auxNode;

        updateValues( node -> rightNode );
        updateValues( node );
        return;
    }

    void rotateRight( treapNode *&node ) {
        updateValues( node );
        updateValues( node -> rightNode );
        treapNode *auxNode = node -> rightNode;

        node -> rightNode = auxNode -> leftNode;
        auxNode -> leftNode = node; node = auxNode;

        updateValues( node -> leftNode );
        updateValues( node );
        return;
    }

    void balanceNode( treapNode *&node ) {
        updateReverse( node );

        if( node -> leftNode -> priority > node -> priority )
            rotateLeft( node );

        if( node -> rightNode -> priority > node -> priority )
            rotateRight( node );

        return;
    }

    TYPE findKey( treapNode *&node, int position ) {
        updateReverse( node );

        if( node == emptyNode )
            return node -> key;

        if( node -> leftNode -> nodeSize + 1 == position )
            return node -> key;

        if( node -> leftNode -> nodeSize + 1 > position )
            return findKey( node -> leftNode, position );
        else
            return findKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ) );
    }

    bool insertKey( treapNode *&node, int position, TYPE key, int priority ) {
        bool ok; updateReverse( node );

        if( node == emptyNode ) {
            if( position != 1 )
                return false;

            node = new treapNode( key, 1, priority, myHash[1], emptyNode, emptyNode );
            return true;
        }

        if( node -> leftNode -> nodeSize + 1 >= position )
            ok = insertKey( node -> leftNode, position, key, priority );
        else
            ok = insertKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ), key, priority );

        updateValues( node ); balanceNode( node );
        return ok;
    }

    bool eraseKey( treapNode *&node, int position ) {
        bool ok; updateValues( node );

        if( node == emptyNode )
            return false;

        if( node -> leftNode -> nodeSize + 1 > position ) {
            ok = eraseKey( node -> leftNode, position );
            updateValues( node ); return ok;
        }

        if( node -> leftNode -> nodeSize + 1 < position ) {
            ok = eraseKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ) );
            updateValues( node ); return ok;
        }

        if( node -> leftNode == emptyNode && node -> rightNode == emptyNode ) {
            delete node; node = emptyNode;
            return true;
        }
        else {
            if( node -> leftNode -> priority > node -> rightNode -> priority ) {
                rotateLeft( node );
                ok = eraseKey( node -> rightNode, node -> rightNode -> leftNode -> nodeSize + 1 );
            } else {
                rotateRight( node );
                ok = eraseKey( node -> leftNode, node -> leftNode -> leftNode -> nodeSize + 1 );
            }

            updateValues( node );
            return ok;
        }
    }

public:

    nrxPositionTreap() {
        srand( time(0) );
        root = emptyNode = new treapNode;

        myHash.resize( MAXSIZE ); myHash[0] = make_pair( 1, 1 );

        for( int i = 1; i < MAXSIZE; i ++ ) {
            myHash[i].first  = ( myHash[i - 1].first  * CONST1 ) % MOD1;
            myHash[i].second = ( myHash[i - 1].second * CONST2 ) % MOD2;
        }

        myHash[0] = make_pair( 0, 0 );
    }

    nrxPositionTreap( int SIZE ) {
        srand( time(0) );
        root = emptyNode = new treapNode;

        myHash.resize( SIZE + 1 ); myHash[0] = make_pair( 1, 1 );

        for( int i = 1; i <= SIZE; i ++ ) {
            myHash[i].first  = ( myHash[i - 1].first  * CONST1 ) % MOD1;
            myHash[i].second = ( myHash[i - 1].second * CONST2 ) % MOD2;
        }

        myHash[0] = make_pair( 0, 0 );
    }

    bool emptyTreap( void ) { return root == emptyNode; }

    TYPE findMin  ( void ) { return root -> minim; }
    TYPE findMax  ( void ) { return root -> maxim; }
    TYPE findFirst( void ) { return root -> first; }
    TYPE findLast ( void ) { return root -> last ; }

    TYPE lowerBound( int position ) { return findKey( root, position ); }
    TYPE upperBound( int position ) { return findKey( root, position ); }

    TYPE rangeFirst( int left, int right ) { return findKey( root, left  ); }
    TYPE rangeLast ( int left, int right ) { return findKey( root, right ); }

    bool insertKey( int position, TYPE key ) { return insertKey( root, position, key, rand() % INT_MAX ); }
    bool eraseKey ( int position           ) { return eraseKey ( root, position                        ); }
    bool findKey  ( int position           ) { return findKey  ( root, position                        ); }

    int accessKey ( int position ) { return findKey( root, position ); }

    void clearTreap( void ) { while( !emptyTreap() ) eraseKey( 1 ); return; }

    void splitTreap( treapNode *&myTreap, int position, treapNode *&myTreap1, treapNode *&myTreap2 ) {
        TYPE randomKey;

        insertKey( myTreap, position + 1, randomKey, INT_MAX );
        myTreap1 = myTreap -> leftNode; myTreap2 = myTreap -> rightNode;
        return;
    }

    void joinTreap( treapNode *&myTreap1, treapNode *&myTreap2, treapNode *&myTreap ) {
        TYPE randomKey; pair <int, int> randomHash;

        treapNode *auxRoot = new treapNode( randomKey, 1 + myTreap1 -> nodeSize + myTreap2 -> nodeSize, INT_MIN, randomHash, myTreap1, myTreap2 );
        eraseKey( auxRoot, auxRoot -> leftNode -> nodeSize + 1 ); myTreap = auxRoot;
        return;
    }

    void rangeErase( int left, int right ) {

        for( int i = left; i <= right; i ++ )
            eraseKey( root, left );

        return;
    }

    void rangeReverse( int left, int right ) {
        treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4;

        splitTreap( root, left - 1, myTreap1, myTreap2 );
        splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );

        myTreap3 -> reversed = !( myTreap3 -> reversed );

        joinTreap( myTreap3, myTreap4, myTreap2 );
        joinTreap( myTreap1, myTreap2, root );

        return;
    }

    TYPE rangeMin( int left, int right ) {
        treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4; TYPE minim;

        splitTreap( root, left - 1, myTreap1, myTreap2 );
        splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );

        minim = myTreap3 -> minim;

        joinTreap( myTreap3, myTreap4, myTreap2 );
        joinTreap( myTreap1, myTreap2, root );

        return minim;
    }

    TYPE rangeMax( int left, int right ) {
        treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4; TYPE maxim;

        splitTreap( root, left - 1, myTreap1, myTreap2 );
        splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );

        maxim = myTreap3 -> maxim;

        joinTreap( myTreap3, myTreap4, myTreap2 );
        joinTreap( myTreap1, myTreap2, root );

        return maxim;
    }
};

ifstream inputFile ( "secv8.in"  );
ofstream outputFile( "secv8.out" );

int N, K, X, Y; char ch;
nrxPositionTreap <int> myTreap( 250000 );

int main( int argc, const char *argv[] ){

    inputFile >> N >> K;
    for( int i = 1; i <= N; i ++ ) {
        inputFile >> ch;

        switch( ch ) {
            case 'I': {
                inputFile >> X >> Y;
                myTreap.insertKey( X, Y );
                break;
            }
            case 'A': {
                inputFile >> X;
                outputFile << myTreap.accessKey( X ) << "\n";
                break;
            }
            case 'R': {
                inputFile >> X >> Y;
                myTreap.rangeReverse( X, Y );
                break;
            }
            case 'D': {
                inputFile >> X >> Y;
                myTreap.rangeErase( X, Y );
                break;
            }
        }
    }

    while( !myTreap.emptyTreap() ) {
        outputFile << myTreap.findFirst() << " ";
        myTreap.eraseKey( 1 );
    }

    return 0;

}