Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <ctime>
- #include <random>
- #include <string>
- using namespace std;
- const int INF = 1000000000;
- class Treap
- {
- public:
- struct nod
- {
- int mn, mx, difMin;
- int val, priority;
- nod *fiuSt, *fiuDr;
- };
- Treap(nod *root = nullptr)
- {
- this->root = root;
- srand(time(0));
- }
- void Insert(int val)
- {
- Insert(root, rand(), val);
- }
- void Split(int val, Treap &st, Treap &dr)
- {
- nod *retSt, *retDr;
- Split(root, val, retSt, retDr);
- st = Treap(retSt);
- dr = Treap(retDr);
- }
- //that > this
- void Join(Treap &that)
- {
- root = Join(root, that.root);
- that = Treap();
- }
- void Erase(int val)
- {
- Erase(root, val);
- }
- bool Find(int val)
- {
- return Find(root, val);
- }
- int MaxDif()
- {
- return root->mx - root->mn;
- }
- int MinDif()
- {
- return root->difMin;
- }
- private:
- void Update(nod * x)
- {
- if(x != nullptr)
- {
- x->mn = x->mx = x->val;
- x->difMin = INF;
- if(x->fiuSt != nullptr)
- {
- x->mn = min(x->mn, x->fiuSt->mn);
- x->difMin = min(x->difMin, min(x->fiuSt->difMin, x->val - x->fiuSt->mx));
- }
- if(x->fiuDr != nullptr)
- {
- x->mx = max(x->mx, x->fiuDr->mx);
- x->difMin = min(x->difMin, min(x->fiuDr->difMin, x->fiuDr->mn - x->val));
- }
- }
- }
- void Split(nod *current, int val, nod * &st, nod * &dr)
- {
- if(current == nullptr)
- st = dr = nullptr;
- else if(val < current->val)
- {
- dr = current;
- Split(current->fiuSt, val, st, current->fiuSt);
- }
- else
- {
- st = current;
- Split(current->fiuDr, val, current->fiuDr, dr);
- }
- Update(current);
- }
- nod * Join(nod * st, nod * dr)
- {
- if(st == nullptr)
- return dr;
- if(dr == nullptr)
- return st;
- if(st->priority >= dr->priority)
- {
- st->fiuDr = Join(st->fiuDr, dr);
- Update(st);
- return st;
- }
- dr->fiuSt = Join(st, dr->fiuSt);
- Update(dr);
- return dr;
- }
- void Insert(nod * ¤t, int priority, int val)
- {
- if(current == nullptr || priority > current->priority)
- {
- nod * st, * dr;
- Split(current, val, st, dr);
- current = new nod;
- current->val = val, current->priority = priority;
- current->fiuSt = st, current->fiuDr = dr;
- Update(current);
- return;
- }
- if(val < current->val)
- Insert(current->fiuSt, priority, val);
- else
- Insert(current->fiuDr, priority, val);
- Update(current);
- }
- void Erase(nod * ¤t, int val)
- {
- if(val == current->val)
- {
- nod * t = current;
- current = Join(current->fiuSt, current->fiuDr);
- delete t;
- Update(current);
- return;
- }
- if(val < current->val)
- Erase(current->fiuSt, val);
- else
- Erase(current->fiuDr, val);
- Update(current);
- }
- bool Find(nod * current, int val)
- {
- if(current == nullptr)
- return false;
- if(val == current->val)
- return true;
- if(val < current->val)
- return Find(current->fiuSt, val);
- return Find(current->fiuDr, val);
- }
- nod * root;
- };
- int main()
- {
- ifstream in("zeap.in");
- ofstream out("zeap.out");
- string type;
- int x;
- Treap treap;
- int elem = 0;
- while(in >> type)
- {
- if(type == "I")
- {
- in >> x;
- if(treap.Find(x) == false)
- {
- treap.Insert(x);
- elem++;
- }
- }
- else if(type == "S")
- {
- in >> x;
- if(treap.Find(x) == false)
- out << -1 << "\n";
- else
- {
- treap.Erase(x);
- elem--;
- }
- }
- else if(type == "C")
- {
- in >> x;
- out << treap.Find(x) << "\n";
- }
- else if(type == "MAX")
- {
- if(elem >= 2)
- out << treap.MaxDif() << "\n";
- else
- out << -1 << "\n";
- }
- else
- {
- if(elem >= 2)
- out << treap.MinDif() << "\n";
- else
- out << -1 << "\n";
- }
- }
- in.close();
- out.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement