Pagini recente » Rezultatele filtrării | Cod sursa (job #1199968)
#include<fstream>
#include<string>
#include<sstream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct nod {
int maxim, minim, mindif, val, h, hdif;
nod *l, *r;
nod() { l = 0; r = 0; }
}*avl;
avl root;
string s, s1;
int v, inf = 2000000000;
avl updatemindif(avl root) {
if (root->l == 0 && root->r == 0) {
root->maxim = root->val;
root->minim = root->val;
root->mindif = inf;
}
else if (root->l == 0 && root->r != 0) {
root->maxim = root->r->maxim;
root->minim = root->val;
root->mindif = min(root->r->mindif, root->r->minim - root->val);
}
else if (root->l != 0 && root->r == 0) {
root->maxim = root->val;
root->minim = root->l->minim;
root->mindif = min(root->l->mindif, root->val - root->l->maxim);
}
else {
root->maxim = root->r->maxim;
root->minim = root->l->minim;
root->mindif = min(min(root->r->minim - root->val, root->val - root->l->maxim), min(root->r->mindif, root->l->mindif));
}
return root;
}
avl updatehdif(avl root) {
if (root->l == 0 && root->r == 0) {
root->h = 1;
root->hdif = 0;
}
else if (root->l == 0 && root->r != 0) {
root->h = root->r->h + 1;
root->hdif = root->r->h;
}
else if (root->l != 0 && root->r == 0) {
root->h = root->l->h + 1;
root->hdif = -root->l->h;
}
else {
root->h = max(root->l->h, root->r->h) + 1;
root->hdif = root->r->h - root->l->h;
}
return root;
}
avl rotright(avl root) {
avl aux = root->l;
root->l = aux->r;
aux->r = root;
root = updatehdif(root);
root = updatemindif(root);
aux = updatehdif(aux);
aux = updatemindif(aux);
return aux;
}
avl rotleft(avl root) {
avl aux = root->r;
root->r = aux->l;
aux->l = root;
root = updatehdif(root);
root = updatemindif(root);
aux = updatehdif(aux);
aux = updatemindif(aux);
return aux;
}
avl balance(avl root) {
root = updatehdif(root);
root = updatemindif(root);
if (root->hdif == -2 && root->l->hdif <= 0) root = rotright(root);
else if (root->hdif == -2 && root->l->hdif == 1) { root->l = rotleft(root->l); root = rotright(root); }
else if (root->hdif == 2 && root->r->hdif >= 0) root = rotleft(root);
else if (root->hdif == 2 && root->r->hdif == -1) { root->r = rotright(root->r); root = rotleft(root); }
return root;
}
avl insert(avl root, int v) {
if (root == 0) {
root = new nod;
root->h = 1;
root->hdif = 0;
root->val = v;
root->maxim = v;
root->minim = v;
root->mindif = inf;
return root;
}
else if (v<root->val) {
root->l = insert(root->l, v);
return balance(root);
}
else if (v>root->val) {
root->r = insert(root->r, v);
return balance(root);
}
return root;
}
avl sterge(avl root, int v) {
if (root == 0) return root;
if (root->val == v) {
if (root->l == 0 && root->r == 0) return 0;
else if (root->l == 0 && root->r != 0) return root->r;
else if (root->l != 0 && root->r == 0) return root->l;
avl p = root->r;
while (p->l != 0) p = p->l;
root->val = p->val;
root->r = sterge(root->r, p->val);
return balance(root);
}
else if (v<root->val) root->l = sterge(root->l, v);
else root->r = sterge(root->r, v);
return balance(root);
}
bool cauta(avl root, int v) {
if (root == 0) return 0;
if (v<root->val) return cauta(root->l, v);
else if (v>root->val) return cauta(root->r, v);
else return 1;
}
int main(void) {
ifstream fin("zeap.in");
ofstream fout("zeap.out");
getline(fin, s, char(EOF));
stringstream cin;
cin << s;
while (cin >> s1) {
if (s1[0] == 'I') { cin >> v; root = insert(root, v); }
else if (s1[0] == 'C') { cin >> v; fout << cauta(root, v) << "\n"; }
else if (s1[0] == 'S') { cin >> v; if (cauta(root, v)) root = sterge(root, v); else fout << "-1\n"; }
else if (s1 == "MIN") { int aux = root->mindif; if (aux == inf) aux = -1; fout << aux << "\n"; }
else { int aux = root->maxim - root->minim; if (aux == 0) --aux; fout << aux << "\n"; }
getline(cin, s1);
}
return 0;
}