Pagini recente » Cod sursa (job #818879) | Arhiva de probleme | Cod sursa (job #2018148) | Cod sursa (job #487718) | Cod sursa (job #2022106)
#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;
}