Cod sursa(job #2022106)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 15 septembrie 2017 17:59:10
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <fstream>
#include <stdlib.h>
#define nmax 30005
using namespace std;
fstream f1("schi.in", ios::in);
fstream f2("schi.out", ios::out);
int n, sol[nmax], q[nmax];
struct treap
{
    treap *left, *right;
    int cheie, prior, siz, total;
} *rad;
void creare_nod(treap *&nod, int prior, int cheie)
{
    nod=new treap;
    nod->left=nod->right=NULL;
    nod->prior=prior;
    nod->cheie=cheie;
    nod->siz=nod->total=0;
}
void rotatie_st(treap *&nod)
{
    treap * aux=nod->left;
    nod->left=aux->right;
    aux->right=nod;
    nod=aux;
}
void rotatie_dr(treap *&nod)
{
    treap * aux=nod->right;
    nod->right=aux->left;
    aux->left=nod;
    nod=aux;
}
void insereaza(treap *&nod, int prior, int cheie)
{
    if(nod==NULL) creare_nod(nod, prior, cheie);
    else if(nod->cheie> cheie)
        {
            insereaza(nod->left, prior, cheie);
            if((nod->left!=NULL)&&(nod->prior< nod->left->prior)) rotatie_st(nod);
        }
         else
        {
            insereaza(nod->right, prior, cheie);
            if((nod->right!=NULL)&&(nod->prior< nod->right->prior)) rotatie_dr(nod);
        }
}
void sterge_nod(treap *&nod)///modifici si sizul
{
    if((nod->left==NULL)&&(nod->right==NULL)) {delete nod; nod=NULL;}
    else if(nod->left==NULL) {treap *aux=nod->right; delete nod; nod=aux;}
         else if(nod->right==NULL) {treap *aux=nod->left; delete nod; nod=aux;}
              else
              {
                 if(nod->left->prior> nod->right->prior)
                    {
                        rotatie_st(nod);
                        nod->right->siz-=(1+ nod->siz);
                        sterge_nod(nod->right);
                    }
                 else
                    {
                        rotatie_dr(nod);
                        nod->siz+=(1+nod->left->siz);
                        sterge_nod(nod->left);
                        nod->siz--;
                    }
              }
}
void numar (treap *&nod, int nr, int val)
{
  if(nr==nod->siz+1) {sol[nod->cheie]=val; sterge_nod(nod);}
  else if(nr<=nod->siz) {numar(nod->left, nr, val);nod->siz--;}
       else numar(nod->right, nr-nod->siz-1, val);
}
void gasire_siz(treap *&nod)
{
    if((nod->left==NULL)&&(nod->right==NULL)) {nod->siz=0;nod->total=0;}
    else if(nod->left==NULL)
        {
            gasire_siz(nod->right);
            nod->siz=0; nod->total=1+nod->right->total;
        }
         else if(nod->right==NULL)
            {
                gasire_siz(nod->left);
                nod->siz=nod->total=1+nod->left->total;
            }
              else
              {
                    gasire_siz(nod->right);
                    gasire_siz(nod->left);
                    nod->siz=1+nod->left->total; nod->total=2+nod->left->total+nod->right->total;
              }
}
void citire()
{
    int i;
    f1>>n;
    for(i=1; i<=n; i++)
        {
            f1>>q[i];
            insereaza(rad, abs(rand())%nmax, i);
        }
    gasire_siz(rad);
    for(i=n; i>=1; i--)
    {
        ///returnezi cheia celui de-al q[i]-lea element din treap si stergi nodul cu cheia respectiva
        numar(rad, q[i], i);
    }
}
void afis()
{
    int i;
    for(i=1; i<=n; i++)
        f2<<sol[i]<<"\n";
}
int main()
{
    citire();
    afis();
    return 0;
}