Cod sursa(job #2484327)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 30 octombrie 2019 22:54:57
Problema Secv8 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.35 kb
#include <fstream>
#include <stdlib.h>
#include <ctime>
#define INF 2000000000
using namespace std;

ifstream fin ("secv8.in");
ofstream fout ("secv8.out");
struct treap{
    int val;
    int priority;
    int nr;
    int lazy;
    treap *left;
    treap *right;
    treap (int val, int priority, int nr, int lazy, treap *left, treap *right){
        this->val = val;
        this->priority = priority;
        this->nr = nr;
        this->lazy = lazy;
        this->left = left;
        this->right = right;
    }};
treap *rad,*nil;
int get_random (){
    return rand()%(INF-1)+1;
}
treap* update (treap *rad){
    if (rad == nil)
        rad->nr = 0;
    else {
        rad->nr = rad->left->nr + rad->right->nr + 1;
        /// acum lazy ul
        if (rad->lazy){
            if (rad->left != nil)
                rad->left->lazy = 1-rad->left->lazy;
            if (rad->right != nil)
                rad->right->lazy = 1-rad->right->lazy;
            /// acum trebuie sa interschimb fiii
            swap (rad->left,rad->right);
            rad->lazy = 0;
        }}
    return rad;
}
pair <treap*,treap*> split (treap *rad, int poz){
    rad = update (rad); /// mereu trb sa fac lazy ul
    pair <treap*, treap*> ans;
    if (rad == nil)
        return make_pair(nil,nil);
    if (rad->left->nr + 1 > poz){ /// o sa ma duc in stanga
        ans = split (rad->left,poz);
        rad->left = ans.second;
        ans.second = rad;
    } else {
        ans = split (rad->right,poz - rad->left->nr - 1);
        rad->right = ans.first;
        ans.first = rad;
    }
    rad = update (rad);
    return ans;
}
treap* join (treap *rad1, treap *rad2){
    if (rad1 == nil)
        return rad2;
    if (rad2 == nil)
        return rad1;
    rad1 = update (rad1);
    rad2 = update (rad2);
    if (rad1->priority > rad2->priority){
        /// pastrez radacina rad1 si fac join intre subarborele drept al lui rad1 si rad2
        /// si treapul rezultat e tot fiul drept a lui rad1
        rad1->right = join (rad1->right,rad2);
        rad1 = update (rad1);
        return rad1;
    } else {
        rad2->left = join (rad1,rad2->left);
        rad2 = update (rad2);
        return rad2;
    }
    return nil;
}
treap* _insert (treap *rad, int poz, int val){
    if (rad == nil){
        rad = new treap (val,get_random(),1,0,nil,nil);
        rad = update (rad);
        return rad;
    }
    pair <treap*,treap*> aux = split (rad,poz-1);
    rad = new treap (val,get_random(),1,0,aux.first,aux.second);
    rad = update (rad);
    return rad;
}
int access (treap *&rad, int nr){
    rad = update (rad);
    if (rad->left->nr == nr-1)
        return rad->val;
    if (rad->left->nr >= nr)
        return access (rad->left,nr);
    return access (rad->right,nr - rad->left->nr - 1);
}
treap* _delete (treap *rad, int x, int y){
    /// dau split de doua ori si unesc cele doua bucati
    pair <treap*, treap*> aux2 = split (rad,y);
    pair <treap*, treap*> aux1 = split (aux2.first,x-1);
    /// acum trb sa le dau join
    rad = join (aux1.first,aux2.second);
    return rad;
}

treap* _reverse (treap *rad, int x, int y){
    /// trb sa aflu bucata din mijloc
    pair <treap*, treap*> aux2 = split (rad,y);
    pair <treap*, treap*> aux1 = split (aux2.first,x-1);
    /// trb sa marchez in lazy
    aux1.second->lazy = 1;
    /// acum trebuie sa le unesc la loc
    aux2.first = join (aux1.first, aux1.second);
    rad = join (aux2.first,aux2.second);
    return rad;
}
void dfs (treap *rad){
    rad = update (rad);
    if (rad == nil)
        return;
    dfs (rad->left);
    fout<<rad->val<<" ";
    dfs (rad->right);
    return;
}
int main (){

    srand(time(0));
    rad = nil = new treap (0,0,0,0,NULL,NULL);

    int t,x,y,poz,ok;
    fin>>t>>ok;
    for (;t--;){
        char op; fin>>op;
        if (op == 'I'){
            fin>>poz>>x;
            rad = _insert (rad,poz,x);
            continue;
        }
        if (op == 'A'){
            fin>>x;
            fout<<access(rad,x)<<"\n";
            continue;
        }
        if (op == 'R'){
            fin>>x>>y;
            rad = _reverse (rad,x,y);
            //dfs (rad);
            //fout<<"\n";
            continue;
        }
        fin>>x>>y;
        rad = _delete (rad,x,y);
    }
    dfs (rad);


    return 0;
}