Cod sursa(job #2596784)

Utilizator mihai50000Popescu Mihai mihai50000 Data 10 aprilie 2020 13:40:59
Problema Zeap Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("zeap.in");
ofstream fout("zeap.out");

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e9;

struct Treap
{
	int key;
	int priority;
	int dif;
	int low;
	int high;
	
	Treap* left;
	Treap* right;
};

Treap* nill = new Treap{0, 0, 2 * INF, INF, -INF, nill, nill};
Treap* root = nill;

void update(Treap* root)
{
	if(root == nill)
		return ;
	
	root -> low = min(root -> key, root -> left -> low);
	root -> high = max(root -> key, root -> right -> high);
	
	root -> dif = min(root -> left -> dif, root -> right -> dif);
	root -> dif = min(root -> dif, root -> right -> low - root -> left -> high);
	
	if(root -> left != nill)
		root -> dif = min(root -> dif, root -> key - root -> left -> high);
	
	if(root -> right != nill)
		root -> dif = min(root -> dif, root -> right -> low - root -> key);
}

Treap* meld(Treap* st, Treap* dr)
{
	if(st == nill)
		return dr;
	
	if(dr == nill)
		return st;
	
	if(st -> priority < dr -> priority)
	{
		st -> right = meld(st -> right, dr);
		update(st);
		return st;
	}
	else
	{
		dr -> left = meld(st, dr -> left);
		update(dr);
		return dr;
	}
}

pair <Treap*, Treap*> split(Treap* root, int key)
{
	pair <Treap*, Treap*> ans = {nill, nill};
	
	if(root == nill)
		return ans;
	
	if(root -> key < key)
	{
		pair <Treap*, Treap*> aux = split(root -> right, key);
		root -> right = aux.first;
		ans = {root, aux.second};
	}
	else
	{
		pair <Treap*, Treap*> aux = split(root -> left, key);
		root -> left = aux.second;
		ans = {aux.first, root};
	}
	
	update(ans.first);
	update(ans.second);
	
	return ans;
}

int cnt = 0;

bool search(Treap* root, int key)
{
	if(root == nill)
		return false;
	
	if(root -> key == key)
		return true;
	
	if(key < root -> key)
		return search(root -> left, key);
	else
		return search(root -> right, key);
}

void insert(Treap* &root, int key)
{
	if(search(root, key))
		return ;
	
	++cnt;
	
	pair <Treap*, Treap*> aux = split(root, key);
	Treap* solo = new Treap{key, rng(), 2 * INF, key, key, nill, nill};
	root = meld(meld(aux.first, solo), aux.second);
}

void erase(Treap* &root, int key)
{
	if(!search(root, key))
	{
		fout << -1 << '\n';
		return ;
	}
	
	--cnt;
	
	pair <Treap*, Treap*> aux1 = split(root, key);
	pair <Treap*, Treap*> aux2 = split(aux1.second, key + 1);
	
	root = meld(aux1.first, aux2.second);
}

void get_max(Treap* root)
{
	if(cnt < 2)
	{
		fout << -1 << '\n';
		return ;
	}
	
	fout << root -> high - root -> low << '\n';
}

void get_min(Treap* root)
{
	if(cnt < 2)
	{
		fout << -1 << '\n';
		return ;
	}
	
	fout << root -> dif << '\n';
}

main()
{
	char op;
	while(fin >> op)
	{
		if(op == 'I')
		{
			int x;
			fin >> x;
			
			insert(root, x);
			continue;
		}
		
		if(op == 'S')
		{
			int x;
			fin >> x;
			
			erase(root, x);
			continue;
		}
		
		if(op == 'C')
		{
			int x;
			fin >> x;
			
			fout << search(root, x) << '\n';
			continue;
		}
		
		fin >> op >> op;
		
		if(op == 'X')
		{
			get_max(root);
			continue;
		}
		
		get_min(root);
	}
}