Cod sursa(job #945052)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 aprilie 2013 12:17:51
Problema Zeap Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.75 kb
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <ctime>

const int INF = 0x3f3f3f3f;

struct treap {
    int key, priority;
    int m;
    treap *left, *right;

    treap(int _key, int _priority, treap *_left, treap *_right) {
        key = _key;
        priority = _priority;
        left = _left;
        right = _right;
        m = INF;
    }
} *R, *nil;

char s[20];

inline int min(int x, int y) {
    return x < y ? x : y;
}

void init() {
    srand(time(0));
    R = nil = new treap(0, 0, NULL, NULL);
}

void getMin(treap *&node) {
    int d1 = INF, d2 = INF;
    
    if (node->left != nil)
        d1 = node->key - node->left->key;

    if (node->right != nil)
        d2 = node->right->key - node->key;

    node->m = min(min(node->left->m, node->right->m), min(d1, d2));
}

void simpleRecompute(treap *&node) {
    if (node == nil)
        return;

    getMin(node);
}

void recompute(treap *&node) {
    if (node == nil)
        return;

    simpleRecompute(node->left);
    simpleRecompute(node->right);
    simpleRecompute(node);
}

void rotleft(treap *&node) {
    treap *aux = node->left;
    node->left = aux->right;
    aux->right = node;
    node = aux;
}

void rotright(treap *&node) {
    treap *aux = node->right;
    node->right = aux->left;
    aux->left = node;
    node = aux;
}

void balance(treap *&node) {
    if (node->left->priority > node->priority)
        rotleft(node);
    else if (node->right->priority > node->priority)
        rotright(node);
}

void insert(treap *&node, int key, int priority) {
    if (node == nil) {
        node = new treap(key, priority, nil, nil);
        return;
    }

    if (key < node->key) 
        insert(node->left, key, priority);
    else
        insert(node->right, key, priority);

    balance(node);
    recompute(node);
}

void erase(treap *&node, int key) {
    if (node == nil) 
        return;

    if (key < node->key)
        erase(node->left, key);
    else if (key > node->key) 
        erase(node->right, key);
    else {
        if (node->left == nil && node->right == nil) {
            delete node;
            node = nil;
        } else {
            (node->left->priority > node->right->priority) ? rotleft(node) : rotright(node);
            erase(node, key);
        }
    }

    recompute(node);
}

bool search(treap *&node, int key) {
    if (node == nil)
        return 0;

    if (key < node->key)
        return search(node->left, key);
    
    if (key > node->key)
        return search(node->right, key);

    return 1;
}

int getNumber(char *s) {
    int x = 0;

    while ('0' <= *s && *s <= '9')
        x = x * 10 + (*s++) - '0';
    
    return x;
}

int min(treap *&R) {
    if (R->left != nil)
        return min(R->left);

    return R->key;
}

int max(treap *&R) {
    if (R->right != nil)
        return max(R->right);

    return R->key;
}

int main() {
    assert(freopen("zeap.in", "r", stdin));
    assert(freopen("zeap.out", "w", stdout));

    init();

    while (fgets(s, sizeof(s), stdin)) {
        if (s[0] == 'I') {
            bool ans = search(R, getNumber(s + 2));
            if (!ans) 
                insert(R, getNumber(s + 2), rand() + 1);

            continue;
        } 

        if (s[0] == 'S') {
            bool ans = search(R, getNumber(s + 2));
            if (!ans)
                printf("-1\n");
            else 
                erase(R, getNumber(s + 2));

            continue;
        }

        if (s[0] == 'C') {
            printf("%d\n", search(R, getNumber(s + 2)));
        
            continue;
        }

        if (s[0] == 'M' && s[1] == 'I') {
            int x = R->m;
            printf("%d\n", (x != INF) ? x : -1);
            
            continue;
        }

        int x = max(R) - min(R);
        printf("%d\n", (x != 0) ? x : -1);
    }

    return 0;
}