Cod sursa(job #2605562)

Utilizator bogdi1bogdan bancuta bogdi1 Data 25 aprilie 2020 14:03:35
Problema Secv8 Scor 25
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 4.6 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Treap
{
    Treap *left,*right;
    bool lazy;
    int sz;
    int pr;
    int nr;
    Treap(int nr, int pr)
    {
        left=nullptr;
        right=nullptr;
        lazy=0;
        sz=0;
        this->pr=pr;
        this->nr=nr;
    }
} *nil, *root;
void init()
{
    srand(12345678);
    root=nil=new Treap(-1, -1);
}
void update(Treap* treap)
{
    if(treap==nil)
        return;
    treap->sz=treap->left->sz+treap->right->sz+1;
}
pair<Treap*, Treap*> split(Treap* treap, int sz)
{
    if(treap==nil)
        return make_pair(nil, nil);
    if(treap->lazy==1){
        swap(treap->left, treap->right);
        treap->left->lazy=(treap->left->lazy+1)%2;
        treap->right->lazy=(treap->right->lazy+1)%2;
        treap->lazy=0;
    }
    if(sz==0)
        return make_pair(nil, treap);
    pair<Treap*, Treap*> ans;
    if(sz<=treap->left->sz){
        ans=split(treap->left, sz);
        treap->left=ans.second;
        ans.second=treap;
    }
    else{
        ans=split(treap->right, sz-treap->left->sz-1);
        treap->right=ans.first;
        ans.first=treap;
    }
    update(treap);
    return ans;
}
Treap* join(Treap*  left, Treap *right)
{
    if(left==nil)
        return right;
    if(right==nil)
        return left;
    if(left->pr>right->pr){
        if(left->lazy==1){
            swap(left->left, left->right);
            left->left->lazy=(left->left->lazy+1)%2;
            left->right->lazy=(left->right->lazy+1)%2;
            left->lazy=0;
        }
        left->right=join(left->right, right);
        update(left);
        return left;
    }
    else{
        if(right->lazy==1){
            swap(right->left, right->right);
            right->left->lazy=(right->left->lazy+1)%2;
            right->right->lazy=(right->right->lazy+1)%2;
            right->lazy=0;
        }
        right->left=join(left, right->left);
        update(right);
        return right;
    }
}
Treap* add(Treap* treap, int nr, int poz, int pr)
{
    if(pr>treap->pr){
        pair<Treap*, Treap*> aux=split(treap, poz);
        treap=new Treap(nr, pr);
        treap->left=aux.first;
        treap->right=aux.second;
        update(treap);
        return treap;
    }
    if(treap->lazy==1){
        swap(treap->left, treap->right);
        treap->left->lazy=(treap->left->lazy+1)%2;
        treap->right->lazy=(treap->right->lazy+1)%2;
        treap->lazy=0;
    }
    if(poz<=treap->left->sz)
        treap->left=add(treap->left, nr, poz, pr);
    else
        treap->right=add(treap->right, nr, poz-treap->left->sz-1, pr);
    update(treap);
    return treap;
}
void parc(Treap* treap)
{
    if(treap==nil)
        return;
    parc(treap->left);
    printf("%d ", treap->nr);
    parc(treap->right);
}
void rev(int st, int dr)
{
    pair<Treap*, Treap*> aux;
    pair<Treap*, Treap*> aux1;
    aux=split(root, st-1);
    aux1=split(aux.second, dr-st+1);
    aux1.first->lazy=(aux1.first->lazy+1)%2;
    root=join(aux.first, join(aux1.first, aux1.second));
}
int exist(Treap* treap, int poz)
{
    if(treap==nil)
        return 0;
    if(treap->lazy==1){
        swap(treap->left, treap->right);
        treap->left->lazy=(treap->left->lazy+1)%2;
        treap->right->lazy=(treap->right->lazy+1)%2;
        treap->lazy=0;
    }
    if(poz==treap->left->sz+1)
        return treap->nr;
    if(poz<=treap->left->sz)
        return exist(treap->left, poz);
    else
        return exist(treap->right, poz-treap->left->sz-1);
}
void del(int st, int dr)
{
    pair<Treap*, Treap*> aux;
    pair<Treap*, Treap*> aux1;
    aux=split(root, st-1);
    aux1=split(aux.second, dr-st+1);
    root=join(aux.first, aux1.second);
}
int main()
{   freopen("secv8.in", "r", stdin);
    freopen("secv8.out", "w", stdout);
    int n,bullshit,i,poz,nr,x,y;
    char c;
    scanf("%d%d\n", &n, &bullshit);
    init();
    for(i=1; i<=n; i++){
        scanf("%c", &c);
        if(c=='I'){
            scanf("%d%d\n", &poz, &nr);
            root=add(root, nr, poz-1, rand());
        }
        else{
            if(c=='A'){
                scanf("%d\n", &poz);
                printf("%d\n", exist(root, poz));
            }
            else{
                if(c=='R'){
                    scanf("%d%d\n", &x, &y);
                    rev(x, y);
                }
                else{
                    scanf("%d%d\n", &x, &y);
                    del(x, y);
                }
            }
        }
    }
    parc(root);
    return 0;
}