Cod sursa(job #1973440)

Utilizator felixiPuscasu Felix felixi Data 24 aprilie 2017 23:03:50
Problema Zeap Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <fstream>
#include <algorithm>
using namespace std;

typedef struct Treap * Arbore;
typedef pair <Arbore, Arbore> Paa;
Arbore NIL;

struct Treap
{
	int min, max, g, difmin, val, prio;
	Arbore st, dr;
	Treap(int _val) : val(_val), prio(rand()), min(_val), max(_val), difmin(1e9), g(1), st(NIL), dr(NIL) { }
	~Treap() {
		if (st != NIL)
			delete st;
		if (dr != NIL)
			delete dr;
	}
};

Arbore join(Arbore a, Arbore b);
Paa split(Arbore x, int val);
void process(Arbore x);
bool check(Arbore x, int val);
Arbore sterge(Arbore x, int val);
Arbore insert(Arbore x, int val);

char input[100];
ifstream in("zeap.in");
ofstream out("zeap.out");

int main()
{
	NIL = new Treap(0);
	NIL->st = NIL->dr = NIL;
	NIL->g = 0;


	Arbore k = NIL;
	int x;

	while (in >> input) {
		switch(input[0]) {
			case 'I':
				in >> x;
				k = insert(k, x);
				break;
			case 'S':
				in >> x;
				k = sterge(k, x);
				break;
			case 'C':
				in >> x;
				out << check(k, x) << '\n';
				break;
			default:
				if (k->min == k->max)
					out << "-1\n";
				else if (input[1] == 'A')
					out << k->max - k->min << '\n';
				else
					out << k->difmin << '\n';
				break;
		}
	}

}

Arbore insert(Arbore x, int val)
{
	if (check(x, val))
		return x;
	Paa ans = split(x, val);
	Arbore nod = new Treap(val);
	return join(join(ans.first, nod), ans.second);
}

Arbore sterge(Arbore x, int val)
{
	Paa s1 = split(x, val);
	Paa s2 = split(s1.first, val - 1);
	if (s2.second == NIL)
		out << "-1\n";
	return join(s2.first, s1.second);
}

bool check(Arbore x, int val)
{
	if (x->val == val)
		return 1;
	if (x == NIL)
		return 0;
	if (x->val > val)
		return check(x->st, val);
	return check(x->dr, val);
}

Paa split(Arbore x, int val)
{
	if (x == NIL)
		return { NIL, NIL };
	if (x->val <= val) {
		Paa ans = split(x->dr, val);
		x->dr = NIL;
		process(x);
		return { join(x, ans.first), ans.second };
	}
	Paa ans = split(x->st, val);
	x->st = NIL;
	process(x);
	return { ans.first, join(ans.second, x) };
}

Arbore join(Arbore a, Arbore b)
{
	if (a == NIL)
		return b;
	if (b == NIL)
		return a;

	if (a->val > b->val)
		swap(a, b);

	if (a->prio > b->prio) {
		a->dr = join(a->dr, b);
		process(a);
		return a;
	}
	b->st = join(a, b->dr);
	process(b);
	return b;
}

void process(Arbore x)
{
	x->g = 1 + x->st->g + x->dr->g;
	x->min = x->max = x->val;
	x->difmin = 1e9;
	if (x->st != NIL) {
		x->min = x->st->min;
		x->difmin = min(x->difmin, x->val - x->st->max);
		x->difmin = min(x->difmin, x->st->difmin);
	}
	if (x->dr != NIL) {
		x->max = x->dr->max;
		x->difmin = min(x->difmin, x->dr->min - x->val);
		x->difmin = min(x->difmin, x->dr->difmin);
	}
}