Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<utility>
- #include<algorithm>
- #include<cmath>
- #include<cstdlib>
- #include<cassert>
- #include<ctime>
- using namespace std;
- FILE *fin = freopen("zeap.in", "r", stdin);
- FILE *fout = freopen("zeap.out", "w", stdout);
- const int INF = 1000000001;
- char S[20];
- struct Node{
- int val;
- int MIN;
- int MAX;
- int minDIFF;
- long long priority;
- Node* left;
- Node* right;
- };
- Node* emptyNode = new Node;
- void recompute(Node* root)
- {
- if (root == emptyNode) return;
- root -> minDIFF = INF;
- root -> MIN = root -> MAX = root -> val;
- if (root -> left != emptyNode)
- {
- root -> minDIFF = min(min(root -> val - root -> left -> MAX, root -> left -> minDIFF), root -> minDIFF);
- root -> MIN = min(root -> MIN, root -> left -> MIN);
- root -> MAX = max(root -> left -> MAX, root -> MAX);
- }
- if (root -> right != emptyNode)
- {
- root -> minDIFF = min(min(root -> right -> minDIFF, root -> right -> MIN - root -> val), root -> minDIFF);
- root -> MIN = min(root -> right -> MIN, root -> MIN) ;
- root -> MAX = max(root -> right -> MAX, root -> MAX);
- }
- }
- pair < Node*, Node* > split(Node* node, int val)
- {
- pair < Node*, Node* > p;
- if (node == emptyNode)
- {
- p.first = emptyNode;
- p.second = emptyNode;
- }
- else
- if (val < node -> val)
- {
- pair < Node*, Node* > q = split(node -> left, val);
- p.first = q.first;
- node -> left = q.second;
- p.second = node;
- recompute(node);
- }
- else
- {
- pair < Node*, Node* > q = split(node -> right, val);
- p.second = q.second;
- node -> right = q.first;
- p.first = node;
- recompute(node);
- }
- return p;
- }
- bool Search(Node* node, int val)
- {
- if (node == emptyNode)
- return 0;
- if (node -> val == val)
- return 1;
- if (node -> val < val)
- return Search(node -> right, val);
- return Search(node -> left, val);
- }
- Node* join(Node* first, Node* second)
- {
- if (first == emptyNode)
- return second;
- else if (second == emptyNode)
- return first;
- else if (first -> priority > second -> priority)
- {
- first -> right = join(first -> right, second);
- recompute(first);
- return first;
- }
- else
- {
- second -> left = join(first, second -> left);
- recompute(second);
- return second;
- }
- }
- Node* Insert(Node* node, int val)
- {
- Node* newNode = new Node;
- newNode -> val = newNode -> MIN = newNode -> MAX = val;
- newNode -> minDIFF = INF;
- newNode -> priority = ((long long) rand() << 45)
- ^ ((long long) rand() << 30)
- ^ ((long long) rand() << 15)
- ^ ((long long) rand() << 0);
- newNode -> priority &= 0x7fffffffffffffff;
- newNode -> left = emptyNode;
- newNode -> right = emptyNode;
- pair < Node*, Node* > p = split(node, val);
- return join(join(p.first, newNode), p.second);
- }
- Node* Delete(Node* node, int val)
- {
- pair < Node*, Node* > p = split(node, val);
- pair < Node*, Node* > q = split(p.first, val - 1);
- return join(q.first, p.second);
- }
- int getNumber()
- {
- int ind = 2, number = 0;
- while (S[ind] >= '0' && S[ind] <= '9')
- number = number * 10 + S[ind] - '0', ind++;
- return number;
- }
- void print(Node* root, int depth = 0) {
- if (root != emptyNode) {
- for(int i = 0; i < depth; i++)
- printf(" ");
- printf("%d: %lld\n", root->val, root->priority);
- print(root->left, depth + 1);
- print(root->right, depth + 1);
- }
- if (depth == 0)
- printf("\n");
- }
- int main()
- {
- emptyNode -> val = emptyNode -> MAX = -INF;
- emptyNode -> MIN = emptyNode -> minDIFF = INF;
- emptyNode -> priority = -1;
- emptyNode -> left = emptyNode;
- emptyNode -> right = emptyNode;
- Node* root = emptyNode;
- while(gets(S))
- {
- if (S[0] != 'M')
- {
- int number = getNumber();
- if (S[0] == 'I')
- {
- if (!Search(root, number))
- root = Insert(root, number);
- }
- if (S[0] == 'S')
- {
- if (Search(root, number))
- root = Delete(root, number);
- else
- printf("-1\n");
- }
- if (S[0] == 'C')
- printf("%d\n", Search(root, number));
- }
- else
- {
- if (S[1] == 'I')
- {
- int diff = root -> minDIFF;
- if (diff == INF)
- printf("-1\n");
- else
- printf("%d\n", diff);
- }
- else
- {
- int diff = root -> MAX - root -> MIN;
- if (diff < 1)
- printf("-1\n");
- else
- printf("%d\n", diff);
- }
- }
- }
- //print(root);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement