Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- struct heap_elements;
- struct list_segments
- {
- int l;
- int r;
- int status;
- struct list_segments* next;
- struct list_segments* prev;
- int to_heap;
- };
- struct heap_elements
- {
- int l;
- int r;
- int pos;
- list_segments* to_list;
- };
- bool operator<(const heap_elements& a, const heap_elements& b)
- {
- if ((a.r - a.l < b.r - b.l))
- return true;
- if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
- return true;
- return false;
- }
- class Heap
- {
- std::vector<struct heap_elements> h;
- int heap_size;
- public:
- Heap();
- void siftup();
- void siftdown(int pos);
- void add(int, int, list_segments*);
- void delete_vertex(int pos);
- bool isempty();
- heap_elements* get_head();
- };
- Heap::Heap()
- {
- std::vector<struct heap_elements> h;
- heap_size = 0;
- }
- heap_elements* Heap::get_head()
- {
- return &h[0];
- }
- bool Heap::isempty()
- {
- if (heap_size == 0)
- return true;
- return false;
- }
- void Heap::siftup()
- {
- int curr, parent;
- curr = heap_size - 1;
- parent = (curr - 1) / 2;
- while (parent >= 0 && curr > 0)
- {
- if (h[parent] < h[curr])
- {
- heap_elements buff = h[curr];
- h[curr] = h[parent];
- h[parent] = buff;
- h[curr].pos = curr;
- h[parent].pos = parent;
- h[curr].to_list->to_heap = curr;
- h[parent].to_list->to_heap = parent;
- }
- curr = parent;
- parent = (curr - 1) / 2;
- }
- }
- void Heap::siftdown(int pos)
- {
- int parent, max_child;
- int curr = pos;
- int child_l = 2 * curr + 1;
- int child_r = 2 * curr + 2;
- if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- while (child_l < heap_size)
- {
- if (child_l == heap_size - 1)
- max_child = child_l;
- else if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- if (h[curr] < h[max_child])
- {
- heap_elements buff = h[curr];
- h[curr] = h[max_child];
- h[max_child] = buff;
- h[curr].pos = curr;
- h[max_child].pos = max_child;
- h[curr].to_list->to_heap = curr;
- h[max_child].to_list->to_heap = max_child;
- }
- curr = max_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- void Heap::add(int l, int r, list_segments* to_list)
- {
- heap_elements vertex;
- vertex.l = l;
- vertex.r = r;
- vertex.to_list = to_list;
- h.push_back(vertex);
- h[heap_size].pos = heap_size;
- if (h[heap_size].to_list != NULL)
- h[heap_size].to_list->to_heap = heap_size;
- heap_size++;
- siftup();
- }
- void Heap::delete_vertex(int pos)
- {
- h[pos] = h[heap_size - 1];
- h.pop_back();
- heap_size--;
- siftdown(pos);
- }
- class LIST_SEGMENTS
- {
- struct list_segments* Head;
- int count;
- public:
- LIST_SEGMENTS();
- list_segments* get_head();
- void add(int, int, int, int, list_segments*);
- void delete_segment(list_segments* segment);
- void add_head(int, int, int, int);
- };
- LIST_SEGMENTS::LIST_SEGMENTS()
- {
- Head = NULL;
- count = 0;
- }
- void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
- {
- list_segments* buff = new list_segments;
- buff->prev = 0;
- buff->l = l;
- buff->r = r;
- buff->status = status;
- buff->next = Head;
- if (Head != NULL)
- Head->prev = buff;
- Head = buff;
- count++;
- }
- void LIST_SEGMENTS::add(int l, int r, int status, int to_heap, list_segments* segment)
- {
- list_segments* after_segment = new list_segments;
- after_segment->l = l;
- after_segment->r = r;
- after_segment->status = status;
- after_segment->next = segment->next;
- after_segment->prev = segment;
- after_segment->to_heap = to_heap;
- if (segment->next != NULL)
- segment->next->prev = after_segment;
- segment->next = after_segment;
- count++;
- }
- void LIST_SEGMENTS::delete_segment(list_segments* segment)
- {
- if (segment->next != NULL)
- segment->next->prev = segment->prev;
- if (segment->prev != NULL)
- segment->prev->next = segment->next;
- else
- Head = segment->next;
- delete segment;
- }
- list_segments* LIST_SEGMENTS::get_head()
- {
- return Head;
- }
- void find_memory(Heap* heap, LIST_SEGMENTS* List, int K, int query_number,
- std::vector<int>& answers, list_segments** requests)
- {
- int old_l;
- heap_elements* heap_head;
- heap_head = heap->get_head();
- if (!heap->isempty() & (heap_head->r - heap_head->l + 1) >= K)
- {
- if ((heap_head->r - heap_head->l + 1) == K)
- {
- heap_head->to_list->status = 0;
- requests[query_number] = heap_head->to_list;
- answers.push_back(heap_head->l);
- heap->delete_vertex(0);
- }
- else
- {
- old_l = heap_head->l;
- heap_head->l = old_l + K;
- heap_head->to_list->l = old_l + K;
- if (heap_head->to_list->prev != NULL)
- {
- List->add(old_l, old_l + K - 1, 0, -1, heap_head->to_list->prev);
- requests[query_number] = heap_head->to_list->prev;
- }
- else
- {
- List->add_head(old_l, old_l + K - 1, 0, -1);
- requests[query_number] = List->get_head();
- }
- heap->siftdown(0);
- answers.push_back(old_l);
- }
- }
- else
- {
- requests[query_number] = NULL;
- answers.push_back(-1);
- }
- }
- void free_up_memory(Heap* heap, LIST_SEGMENTS* List, int q, int query_number,
- std::vector<int>& answers, list_segments** requests)
- {
- if (requests[q] != NULL)
- {
- requests[q]->status = 1;
- if (requests[q]->prev != NULL)
- {
- if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
- {
- requests[q]->l = requests[q]->prev->l;
- heap->delete_vertex(requests[q]->prev->to_heap);
- List->delete_segment(requests[q]->prev);
- }
- }
- if (requests[q]->next != NULL)
- {
- if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
- {
- requests[q]->r = requests[q]->next->r;
- heap->delete_vertex(requests[q]->next->to_heap);
- List->delete_segment(requests[q]->next);
- }
- }
- heap->add(requests[q]->l, requests[q]->r, requests[q]);
- requests[query_number] = requests[q];
- requests[q] = NULL;
- }
- else
- {
- requests[query_number] = NULL;
- }
- }
- int main()
- {
- int N, M, K, q;
- int old_l;
- Heap heap;
- LIST_SEGMENTS List;
- heap_elements* heap_head;
- std::vector<int> answers;
- std::cin >> N;
- List.add_head(1, N, 1, 0);
- heap.add(1, N, List.get_head());
- std::cin >> M;
- list_segments* requests[M];
- for (int query_number = 0; query_number < M; ++query_number)
- {
- std::cin >> K;
- if (K > 0)
- find_memory(&heap, &List, K, query_number, answers, requests);
- else
- {
- q = -K - 1;
- free_up_memory(&heap, &List, q, query_number, answers, requests);
- }
- }
- for (int i = 0; i < answers.size(); ++i)
- std::cout << answers[i] << std::endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment