vadimk772336

Untitled

Oct 28th, 2021
749
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. struct heap_elements;
  5.  
  6. struct list_segments
  7. {
  8.     long long int l;
  9.     long long int r;
  10.     long long int status;
  11.     struct list_segments* next;
  12.     struct list_segments* prev;
  13.     long long int to_heap;
  14. };
  15.  
  16. struct heap_elements
  17. {
  18.     long long int l;
  19.     long long int r;
  20.     long long int pos;
  21.     list_segments* to_list;
  22. };
  23.  
  24. bool operator<(const heap_elements& a, const heap_elements& b)
  25. {
  26.  
  27.     if ((a.r - a.l < b.r - b.l))
  28.         return true;
  29.     if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
  30.         return true;
  31.  
  32.     return false;
  33. }
  34.  
  35. class Heap
  36. {
  37.     std::vector<struct heap_elements> h;
  38.     long long int heap_size;
  39.  
  40. public:
  41.     Heap();
  42.     void siftup();
  43.     void siftdown(long long int pos);
  44.     void add(long long int, long long int, list_segments*);
  45.     void delete_vertex(long long int pos);
  46.     bool isempty();
  47.     heap_elements* get_head();
  48. };
  49.  
  50. Heap::Heap()
  51. {
  52.     std::vector<struct heap_elements> h;
  53.     heap_size = 0;
  54. }
  55.  
  56. heap_elements* Heap::get_head()
  57. {
  58.     return &h[0];
  59. }
  60.  
  61. bool Heap::isempty()
  62. {
  63.     if (heap_size == 0)
  64.         return true;
  65.     return false;
  66. }
  67.  
  68. void Heap::siftup()
  69. {
  70.     long long int curr, parent;
  71.     curr = heap_size - 1;
  72.     parent = (curr - 1) / 2;
  73.     while (parent >= 0 && curr > 0)
  74.     {
  75.         if (h[parent] < h[curr])
  76.         {
  77.             heap_elements buff = h[curr];
  78.             h[curr] = h[parent];
  79.             h[parent] = buff;
  80.  
  81.             h[curr].pos = curr;
  82.             h[parent].pos = parent;
  83.  
  84.             h[curr].to_list->to_heap = curr;
  85.             h[parent].to_list->to_heap = parent;
  86.         }
  87.         curr = parent;
  88.         parent = (curr - 1) / 2;
  89.     }
  90. }
  91.  
  92. void Heap::siftdown(long long int pos)
  93. {
  94.     long long int parent, max_child;
  95.  
  96.     long long int curr = pos;
  97.     long long int child_l = 2 * curr + 1;
  98.     long long int child_r = 2 * curr + 2;
  99.  
  100.     if (h[child_r] < h[child_l])
  101.         max_child = child_l;
  102.     else
  103.         max_child = child_r;
  104.  
  105.     while (child_l < heap_size)
  106.     {
  107.         if (child_l == heap_size - 1)
  108.             max_child = child_l;
  109.         else if (h[child_r] < h[child_l])
  110.             max_child = child_l;
  111.         else
  112.             max_child = child_r;
  113.  
  114.         if (h[curr] < h[max_child])
  115.         {
  116.             heap_elements buff = h[curr];
  117.             h[curr] = h[max_child];
  118.             h[max_child] = buff;
  119.  
  120.             h[curr].pos = curr;
  121.             h[max_child].pos = max_child;
  122.  
  123.             h[curr].to_list->to_heap = curr;
  124.             h[max_child].to_list->to_heap = max_child;
  125.         }
  126.  
  127.         curr = max_child;
  128.         child_l = 2 * curr + 1;
  129.         child_r = 2 * curr + 2;
  130.     }
  131. }
  132.  
  133. void Heap::add(long long int l, long long int r, list_segments* to_list)
  134. {
  135.  
  136.     heap_elements vertex;
  137.     vertex.l = l;
  138.     vertex.r = r;
  139.     vertex.to_list = to_list;
  140.  
  141.     h.push_back(vertex);
  142.     h[heap_size].pos = heap_size;
  143.  
  144.     if (h[heap_size].to_list != NULL)
  145.         h[heap_size].to_list->to_heap = heap_size;
  146.  
  147.     heap_size++;
  148.     siftup();
  149. }
  150.  
  151. void Heap::delete_vertex(long long int pos)
  152. {
  153.     h[pos] = h[heap_size - 1];
  154.     h.pop_back();
  155.     heap_size--;
  156.     siftdown(pos);
  157. }
  158.  
  159. class LIST_SEGMENTS
  160. {
  161.     struct list_segments* Head;
  162.     long long int count;
  163.  
  164. public:
  165.     LIST_SEGMENTS();
  166.     list_segments* get_head();
  167.     void add(long long int, long long int, long long int, long long int, list_segments*);
  168.     void delete_segment(list_segments* segment);
  169.     void add_head(long long int, long long int, long long int, long long int);
  170. };
  171.  
  172. LIST_SEGMENTS::LIST_SEGMENTS()
  173. {
  174.     Head = NULL;
  175.     count = 0;
  176. }
  177.  
  178. void LIST_SEGMENTS::add_head(long long int l, long long int r,
  179.                             long long int status, long long int to_heap)
  180. {
  181.     list_segments* buff = new list_segments;
  182.     buff->prev = 0;
  183.     buff->l = l;
  184.     buff->r = r;
  185.     buff->status = status;
  186.     buff->next = Head;
  187.  
  188.     if (Head != NULL)
  189.         Head->prev = buff;
  190.  
  191.     Head = buff;
  192.     count++;
  193. }
  194.  
  195. void LIST_SEGMENTS::add(long long int l, long long int r,
  196.             long long int status, long long int to_heap, list_segments* segment)
  197. {
  198.     list_segments* after_segment = new list_segments;
  199.     after_segment->l = l;
  200.     after_segment->r = r;
  201.     after_segment->status = status;
  202.     after_segment->next = segment->next;
  203.     after_segment->prev = segment;
  204.     after_segment->to_heap = to_heap;
  205.  
  206.     if (segment->next != NULL)
  207.         segment->next->prev = after_segment;
  208.  
  209.     segment->next = after_segment;
  210.     count++;
  211. }
  212.  
  213. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  214. {
  215.     if (segment->next != NULL)
  216.         segment->next->prev = segment->prev;
  217.     if (segment->prev != NULL)
  218.         segment->prev->next = segment->next;
  219.     else
  220.         Head = segment->next;
  221.     delete segment;
  222. }
  223.  
  224. list_segments* LIST_SEGMENTS::get_head()
  225. {
  226.     return Head;
  227. }
  228.  
  229. void find_memory(Heap* heap, LIST_SEGMENTS* List, long long int K, long long int query_number,
  230.     std::vector<long long int>& answers, list_segments** requests)
  231. {
  232.     long long int old_l;
  233.     heap_elements* heap_head;
  234.  
  235.     heap_head = heap->get_head();
  236.     if (!heap->isempty() & (heap_head->r - heap_head->l + 1) >= K)
  237.     {
  238.         if ((heap_head->r - heap_head->l + 1) == K)
  239.         {
  240.             heap_head->to_list->status = 0;
  241.             requests[query_number] = heap_head->to_list;
  242.             answers.push_back(heap_head->l);
  243.             heap->delete_vertex(0);
  244.         }
  245.         else
  246.         {
  247.             old_l = heap_head->l;
  248.             heap_head->l = old_l + K;
  249.             heap_head->to_list->l = old_l + K;
  250.  
  251.             if (heap_head->to_list->prev != NULL)
  252.             {
  253.                 List->add(old_l, old_l + K - 1, 0, -1, heap_head->to_list->prev);
  254.                 requests[query_number] = heap_head->to_list->prev;
  255.             }
  256.             else
  257.             {
  258.                 List->add_head(old_l, old_l + K - 1, 0, -1);
  259.                 requests[query_number] = List->get_head();
  260.             }
  261.  
  262.             heap->siftdown(0);
  263.             answers.push_back(old_l);
  264.         }
  265.     }
  266.     else
  267.     {
  268.         requests[query_number] = NULL;
  269.         answers.push_back(-1);
  270.     }
  271. }
  272.  
  273. void free_up_memory(Heap* heap, LIST_SEGMENTS* List, long long int q, long long int query_number,
  274.     std::vector<long long int>& answers, list_segments** requests)
  275. {
  276.  
  277.     if (requests[q] != NULL)
  278.     {
  279.         requests[q]->status = 1;
  280.         if (requests[q]->prev != NULL)
  281.         {
  282.             if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
  283.             {
  284.                 requests[q]->l = requests[q]->prev->l;
  285.                 heap->delete_vertex(requests[q]->prev->to_heap);
  286.                 List->delete_segment(requests[q]->prev);
  287.             }
  288.         }
  289.         if (requests[q]->next != NULL)
  290.         {
  291.             if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
  292.             {
  293.                 requests[q]->r = requests[q]->next->r;
  294.                 heap->delete_vertex(requests[q]->next->to_heap);
  295.                 List->delete_segment(requests[q]->next);
  296.             }
  297.         }
  298.  
  299.         heap->add(requests[q]->l, requests[q]->r, requests[q]);
  300.         requests[query_number] = requests[q];
  301.         requests[q] = NULL;
  302.     }
  303.     else
  304.     {
  305.         requests[query_number] = NULL;
  306.     }
  307. }
  308.  
  309.  
  310. int main()
  311. {
  312.  
  313.     long long int N, M, K, q;
  314.     long long int old_l;
  315.  
  316.     Heap heap;
  317.     LIST_SEGMENTS List;
  318.  
  319.     heap_elements* heap_head;
  320.     std::vector<long long int> answers;
  321.  
  322.     std::cin >> N;
  323.  
  324.     List.add_head(1, N, 1, 0);
  325.     heap.add(1, N, List.get_head());
  326.  
  327.     std::cin >> M;
  328.     list_segments* requests[M];
  329.  
  330.     for (int query_number = 0; query_number < M; ++query_number)
  331.     {
  332.         std::cin >> K;
  333.         if (K > 0)
  334.             find_memory(&heap, &List, K, query_number, answers, requests);
  335.         else
  336.         {
  337.             q = -K - 1;
  338.             free_up_memory(&heap, &List, q, query_number, answers, requests);
  339.         }
  340.     }
  341.  
  342.     for (int i = 0; i < answers.size(); ++i)
  343.         std::cout << answers[i] << std::endl;
  344.  
  345.     return 0;
  346. }
  347.  
RAW Paste Data