Black Magic

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <iterator>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::swap;
using std::list;
using std::iter_swap;
using std::iterator;

struct MemSegment {
    int start;
    int end;
    bool isFree;
    int heapIndex;

    MemSegment(int st, int end) {
        this->start = st;
        this->end = end;
        isFree = true;

        heapIndex = -1;
    }
    MemSegment(int st, int end, bool free) {
        this->start = st;
        this->end = end;
        this->isFree = free;

        heapIndex = -1;
    }
    int get_size() {
        return end - start;
    }
};

typedef bool (* CompareSegments) (const list<MemSegment>::iterator& first,
    const list<MemSegment>::iterator& second);

bool compare_size(const list<MemSegment>::iterator& first,
    const list<MemSegment>::iterator& second) {
    if (first->get_size() != second->get_size()) {
        return first->get_size()  < second->get_size();
    } else {
        return first->start > second->start;
    }
}

class Heap {
private:
    vector<list<MemSegment>::iterator> elements;
    CompareSegments compare;

    int left_index(int ind) {
        return ind * 2 + 1;
    }
    int right_index(int ind) {
        return left_index(ind) + 1;
    }
    int parent_index(int ind) {
        return (ind + 1) / 2 - 1;
    }
    void swap_elements(int first, int second) {
        iter_swap(elements.begin() + first, elements.begin() + second);

        update_index(first);
        update_index(second);
    }
    void update_index(int ind) {
        elements.at(ind)->heapIndex = ind;
    }
    void sift_up(int index);
    void sift_down(int index);

public:
    explicit Heap(CompareSegments compare) {
        this->compare = compare;
    }
    bool isEmpty() {
        return elements.size() == 0;
    }
    void insert_element(list<MemSegment>::iterator element) {
        elements.push_back(element);
        int last = elements.size() - 1;
        update_index(last);
        sift_up(last);
    }
    list<MemSegment>::iterator get_top() {
        return elements[0];
    }
    list<MemSegment>::iterator remove_top() {
        swap_elements(0, elements.size() - 1);
        list<MemSegment>::iterator last = elements.back();
        last->heapIndex = -1;
        elements.pop_back();
        sift_down(0);
        return last;
    }
    void remove_element(list<MemSegment>::iterator& element) {
        int ind = element->heapIndex;
        swap_elements(elements.size() - 1, ind);

        elements.pop_back();
        element->heapIndex = -1;


        if (ind < elements.size()) {
            sift_down(ind);
            sift_up(ind);
        }
    }
};

class MemoryManager {
private:
    Heap heap;
    list<MemSegment> segments;
    vector<list<MemSegment>::iterator> inquiry_results;
public:
    explicit MemoryManager(int slots) : heap(& compare_size) {
        MemSegment segment_of_mem(0, slots);

        segments.push_back(segment_of_mem);
        heap.insert_element(segments.begin());
    }
    int insert_inquiry(int size);
    void free(int number_of_inquiry);
};

int main() {
    std::ios_base::sync_with_stdio(false);
    int memory_size;
    cin >> memory_size;
    int inquiry_count;
    cin >> inquiry_count;
    MemoryManager memory_manager(memory_size);

    for (int inquiry_num = 0; inquiry_num < inquiry_count; ++inquiry_num) {
        int inquiry;
        cin >> inquiry;
        if (inquiry > 0) {
            int allocation_result = memory_manager.insert_inquiry(inquiry);
            if (allocation_result != -1) {
                int temp = allocation_result + 1;
                cout << temp << endl;
            } else {
                int temp = allocation_result;
                cout << temp << endl;
            }
        } else if (inquiry < 0) {
            memory_manager.free(-inquiry - 1);
        }
    }
    return 0;
}

void Heap::sift_up(int index) {
    bool should_proceed = true;
    do {
        int parent = parent_index(index);
        if (parent >= 0 && compare(elements[parent], elements[index])) {
            swap_elements(index, parent);
            index = parent;
        } else {
            should_proceed = false;
        }
    } while (should_proceed);
}

void Heap::sift_down(int index) {
    bool should_proceed = true;
    do {
        int left = left_index(index);
        int right = right_index(index);
        int largest;

        if (left < elements.size() && compare(elements[index], elements[left])) {
            largest = left;
        } else {
            largest = index;
        }

        if (right < elements.size() &&  compare(elements[largest], elements[right])) {
            largest = right;
        }

        if (largest != index) {
            swap_elements(index, largest);
            index = largest;
        } else {
            should_proceed = false;
        }
    } while (should_proceed);
}

int MemoryManager::insert_inquiry(int size) {
    bool empty = heap.isEmpty();
    if (empty) {
        inquiry_results.push_back(segments.end());
        return -1;
    }
    int top_size = heap.get_top()->get_size();

    if (top_size < size) {
        inquiry_results.push_back(segments.end());

        return -1;
    }
    list<MemSegment>::iterator seg_element = heap.remove_top();
    if (top_size == size) {
        seg_element->isFree = false;
        inquiry_results.push_back(seg_element);

        return seg_element->start;
    } else {
        MemSegment busy_block = MemSegment(
            seg_element->start, seg_element->start + size, false);
        MemSegment free_block = MemSegment(seg_element->start + size, seg_element->end);

        list<MemSegment>::iterator busy_element = segments.insert(seg_element, busy_block);
        inquiry_results.push_back(busy_element);

        list<MemSegment>::iterator free_element = segments.insert(seg_element, free_block);
        heap.insert_element(free_element);

        segments.erase(seg_element);

        return busy_block.start;
    }
}

void MemoryManager::free(int number_of_inquiry) {
    inquiry_results.push_back(segments.end());

    list<MemSegment>::iterator busy_element = inquiry_results[number_of_inquiry];
    if (busy_element == segments.end()) {
        return;
    }

    int start = busy_element->start;
    int end = busy_element->end;

    if (busy_element != segments.begin()) {
       list<MemSegment>::iterator previous = busy_element;
        --previous;

        if (previous->isFree) {
            start = previous->start;

            heap.remove_element(previous);
            segments.erase(previous);
        }
    }

    list<MemSegment>::iterator next = busy_element;
    ++next;

    if (next != segments.end() && next->isFree) {
        end = next->end;

        heap.remove_element(next);
        segments.erase(next);

        next = busy_element;
        ++next;
    }
    segments.erase(busy_element);

    MemSegment free_block = MemSegment(start, end);
    list<MemSegment>::iterator free_element = segments.insert(next, free_block);
    heap.insert_element(free_element);
}