Pagini recente » Cod sursa (job #2923996) | Cod sursa (job #651513) | Cod sursa (job #9251) | Cod sursa (job #1697820) | Cod sursa (job #1066963)
//O alternativa pentru AVL-uri sau Treapuri si in general a arborilor echilibrati de cautare in timp de concurs
//Complexitatea medie pe orice operatie este O( log N )
//Skip lists
#include<fstream>
#include<stdlib.h>
using namespace std;
typedef struct celula {
int val;
celula *next, *low;
}*lista;
lista head, drum[50];
int op,i,n,x,ld;
int inaltime(){
int h=0,coin=rand()%2;
while (coin) {
++h;
coin=rand()%2;
}
return(h);
}
void init() {
head=new celula;
head->val=-1; head->low=0; head->next=0;
int k=inaltime();
for (int i=1; i<=k; ++i) {
lista v=new celula;
v->val=head->val;
v->low=head;
v->next=0;
head=v;
}
}
void cauta(int x) {
lista aux=head;
ld=0;
while (aux!=0)
if (aux->next!=0&&aux->next->val<=x) aux=aux->next;
else {
++ld;
drum[ld]=aux;
aux=aux->low;
}
}
void insereaza(int x) {
cauta(x);
if (drum[ld]->val!=x) {
int k=inaltime();
if (k==0) ++k;
lista prec=0,v;
for (int i=1; i<=k; ++i)
if (ld>0) {
lista v=new celula;
v->val=x;
v->low=prec;
v->next=drum[ld]->next;
drum[ld]->next=v;
--ld; prec=v;
}
else {
v=new celula; v->val=head->val;
v->low=head; head=v;
v=new celula; v->val=x; v->next=0;
v->low=prec; head->next=v;
prec=v;
}
}
}
void sterge(int x) {
cauta(x-1);
while (ld>0&&drum[ld]->next!=0&&drum[ld]->next->val==x) {
drum[ld]->next=drum[ld]->next->next;
--ld;
}
}
bool exista(int x) {
cauta(x);
return( drum[ld]->val==x );
}
int main(void) {
ifstream fin("hashuri.in");
ofstream fout("hashuri.out");
fin>>n; init(); srand(time(NULL));
for (i=1; i<=n; ++i) {
fin>>op>>x;
if (op==1) insereaza(x);
else if (op==2) sterge(x);
else fout<<exista(x)<<"\n";
}
return(0);
}