Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- struct heap_elements;
- struct list_sections
- {
- int l;
- int r;
- int status;
- struct list_sections* next;
- struct list_sections* prev;
- int to_heap;
- };
- struct heap_elements
- {
- int l;
- int r;
- int pos;
- list_sections* 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> massiv;
- int heap_size;
- public:
- Heap();
- void siftup(int pos);
- void siftdown(int pos);
- void my_swap(int i, int j);
- void add(int, int, list_sections*);
- void delete_vertex(int pos);
- bool isempty();
- heap_elements* get_top();
- };
- Heap::Heap()
- {
- std::vector<struct heap_elements> massiv;
- heap_size = 0;
- }
- heap_elements* Heap::get_top()
- {
- return &massiv[0];
- }
- bool Heap::isempty()
- {
- if (heap_size == 0)
- return true;
- return false;
- }
- void Heap::my_swap(int i, int j)
- {
- heap_elements buffer;
- buffer = massiv[i];
- massiv[i] = massiv[j];
- massiv[j] = buffer;
- massiv[i].pos = i;
- massiv[j].pos = j;
- massiv[i].to_list->to_heap = i;
- massiv[j].to_list->to_heap = j;
- }
- void Heap::siftup(int pos)
- {
- int curr = pos;
- int parent = (curr - 1) / 2;
- while (parent >= 0 & curr > 0)
- {
- if (massiv[parent] < massiv[curr])
- my_swap(parent, curr);
- 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;
- while (child_l < heap_size)
- {
- max_child = child_l;
- if (child_r < heap_size & massiv[child_l] < massiv[child_r])
- max_child = child_r;
- if (massiv[curr] < massiv[max_child])
- my_swap(curr, max_child);
- curr = max_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- void Heap::add(int l, int r, list_sections* to_list)
- {
- heap_size++;
- heap_elements vertex;
- vertex.l = l;
- vertex.r = r;
- vertex.to_list = to_list;
- vertex.pos = heap_size - 1;
- massiv.push_back(vertex);
- to_list->to_heap = heap_size - 1;
- siftup(heap_size - 1);
- }
- void Heap::delete_vertex(int pos)
- {
- massiv[pos] = massiv[heap_size - 1];
- massiv[pos].pos = pos;
- massiv[pos].to_list->to_heap = pos;
- massiv.pop_back();
- heap_size--;
- int parent = (pos - 1) / 2;
- if (massiv[parent] < massiv[pos])
- siftup(pos);
- else
- siftdown(pos);
- }
- class List
- {
- struct list_sections* head;
- int list_size;
- public:
- List();
- list_sections* get_head();
- void add_head(int l, int r, int status, int to_heap);
- void add(int l, int r, int status, int to_heap, list_sections* section);
- void delete_section(list_sections* section);
- };
- List::List()
- {
- head = NULL;
- list_size = 0;
- }
- list_sections* List::get_head()
- {
- return head;
- }
- void List::add_head(int l, int r, int status, int to_heap)
- {
- list_sections* buffer = new list_sections;
- buffer->prev = 0;
- buffer->l = l;
- buffer->r = r;
- buffer->status = status;
- buffer->next = head;
- if (head != NULL)
- head->prev = buffer;
- head = buffer;
- list_size++;
- }
- void List::add(int l, int r, int status, int to_heap, list_sections* section)
- {
- list_sections* after_section = new list_sections;
- after_section->l = l;
- after_section->r = r;
- after_section->status = status;
- after_section->next = section->next;
- after_section->prev = section;
- after_section->to_heap = to_heap;
- if (section->next != NULL)
- section->next->prev = after_section;
- section->next = after_section;
- list_size++;
- }
- void List::delete_section(list_sections* section)
- {
- if (section->next != NULL)
- section->next->prev = section->prev;
- if (section->prev != NULL)
- section->prev->next = section->next;
- else
- head = section->next;
- delete section;
- }
- void find_memory(Heap* heap, List* List, int K, int query_number, list_sections** requests)
- {
- heap_elements* heap_top = heap->get_top();
- if (!heap->isempty() & (heap_top->r - heap_top->l + 1) >= K)
- {
- std::cout << heap_top->l << std::endl;
- if ((heap_top->r - heap_top->l + 1) == K)
- {
- heap_top->to_list->status = 0;
- requests[query_number] = heap_top->to_list;
- heap->delete_vertex(0);
- }
- else
- {
- int new_l = heap_top->l;
- int r = new_l + K - 1;
- int status = 0;
- int to_heap = -1;
- list_sections* prev_head_section = heap_top->to_list->prev;
- heap_top->l = new_l + K;
- heap_top->to_list->l = new_l + K;
- if (prev_head_section != NULL)
- {
- List->add(new_l, r, status, to_heap, prev_head_section);
- requests[query_number] = prev_head_section;
- }
- else
- {
- List->add_head(new_l, r, status, to_heap);
- requests[query_number] = List->get_head();
- }
- heap->siftdown(0);
- }
- }
- else
- {
- requests[query_number] = NULL;
- std::cout << -1 << std::endl;
- }
- }
- void free_up_memory(Heap* heap, List* List, int q, int query_number, list_sections** 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_section(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_section(requests[q]->next);
- }
- }
- heap->add(requests[q]->l, requests[q]->r, requests[q]);
- }
- requests[query_number] = NULL;
- }
- int main()
- {
- int N, M, K;
- heap_elements* heap_top;
- Heap heap;
- List List;
- std::cin >> N;
- std::cin >> M;
- List.add_head(1, N, 1, 0);
- heap.add(1, N, List.get_head());
- list_sections* requests[M];
- for (int i = 0; i < M; ++i)
- {
- std::cin >> K;
- if (K > 0)
- find_memory(&heap, &List, K, i, requests);
- else
- free_up_memory(&heap, &List, -K - 1, i, requests);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment