Cod sursa(job #1553524)

Utilizator maritimCristian Lambru maritim Data 19 decembrie 2015 23:12:35
Problema Zeap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef set<int>::iterator it;
typedef multiset<int>::iterator itm;

ifstream f("zeap.in");
ofstream g("zeap.out");

string command;
int val;
set<int> zeap;
multiset<int> heap;

inline int abs (int a) {
    return a < 0 ? -a : a;
}

inline void insert(int x) {
    it curr = zeap.find (x);

    if (curr != zeap.end()) {
        return;
    }

    zeap.insert(x);
    // can improve this
    curr = zeap.find (x);
    it prev = curr; -- prev;
    it next = curr; ++ next;

    if (curr != zeap.begin() && next != zeap.end()) {
        heap.erase (heap.find (abs (*prev - *next))); 
    }

    if (curr != zeap.begin()) {
        heap.insert (abs (*prev - x));
    }
    if (next != zeap.end()) {
        heap.insert (abs (*next - x));
    }

    //cout << x << ": " 
    //     << (curr == zeap.begin() ? -1 : *prev) 
    //     << " " 
    //     << x 
    //     << " " 
    //     << (next == zeap.end() ? -1 : *next) 
    //     << "\n";
}

inline int erase(int x) {
    it iter = zeap.find (x);
    if (iter == zeap.end()) {
        return -1;   
    }

    it prev = iter; -- prev;
    it next = iter; ++ next;

    if (iter != zeap.begin() && next != zeap.end()) {
        heap.insert (abs (*prev - *next));
    }

    if (iter != zeap.begin()) {
        heap.erase (heap.find (abs (*prev - x)));
    }

    if (next != zeap.end()) {
        heap.erase (heap.find (abs (*next - x)));
    }

    zeap.erase (iter);
    return 0;
}

inline int exists(int x) {
    if (zeap.find (x) == zeap.end()) {
        return 0;
    }
    return 1;
}

inline int maxim() {
    if (zeap.size() < 2) {
        return -1;
    }
    return abs (*zeap.begin() - *zeap.rbegin());
}

inline int minim() {
    if (zeap.size() < 2) {
        return -1;
    }
    return *heap.begin();
}

int main() {
    while (f >> command) {
        if (command == "I") {
            f >> val;
            insert (val);
        }
        else if (command == "S") {
            f >> val;
            if (erase (val)) {
                g << "-1\n";
            }
        }
        else if (command == "C") {
            f >> val;
            g << exists (val) << "\n";
        }
        else if (command == "MAX") {
            g << maxim() << "\n";
        } else {
            g << minim() << "\n";
        }
    }
}