vadimk772336

WA 80

Oct 28th, 2021 (edited)
744
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.     int l;
  9.     int r;
  10.     int status;
  11.     struct list_segments* next;
  12.     struct list_segments* prev;
  13.     int to_heap;
  14. };
  15.  
  16. struct heap_elements
  17. {
  18.     int l;
  19.     int r;
  20.     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.     int heap_size;
  39.  
  40. public:
  41.     Heap();
  42.     void siftup();
  43.     void siftdown(int pos);
  44.     void add(int, int, list_segments*);
  45.     void delete_vertex(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.     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(int pos)
  93. {
  94.     int parent, max_child;
  95.  
  96.     int curr = pos;
  97.     int child_l = 2 * curr + 1;
  98.     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(int l, 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(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.     int count;
  163.  
  164. public:
  165.     LIST_SEGMENTS();
  166.     list_segments* get_head();
  167.     void add(int, int, int, int, list_segments*);
  168.     void delete_segment(list_segments* segment);
  169.     void add_head(int, int, int, int);
  170. };
  171.  
  172. LIST_SEGMENTS::LIST_SEGMENTS()
  173. {
  174.     Head = NULL;
  175.     count = 0;
  176. }
  177.  
  178. void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
  179. {
  180.     list_segments* buff = new list_segments;
  181.     buff->prev = 0;
  182.     buff->l = l;
  183.     buff->r = r;
  184.     buff->status = status;
  185.     buff->next = Head;
  186.  
  187.     if (Head != NULL)
  188.         Head->prev = buff;
  189.  
  190.     Head = buff;
  191.     count++;
  192. }
  193.  
  194. void LIST_SEGMENTS::add(int l, int r, int status, int to_heap, list_segments* segment)
  195. {
  196.     list_segments* after_segment = new list_segments;
  197.     after_segment->l = l;
  198.     after_segment->r = r;
  199.     after_segment->status = status;
  200.     after_segment->next = segment->next;
  201.     after_segment->prev = segment;
  202.     after_segment->to_heap = to_heap;
  203.  
  204.     if (segment->next != NULL)
  205.         segment->next->prev = after_segment;
  206.  
  207.     segment->next = after_segment;
  208.     count++;
  209. }
  210.  
  211. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  212. {
  213.     if (segment->next != NULL)
  214.         segment->next->prev = segment->prev;
  215.     if (segment->prev != NULL)
  216.         segment->prev->next = segment->next;
  217.     else
  218.         Head = segment->next;
  219.     delete segment;
  220. }
  221.  
  222. list_segments* LIST_SEGMENTS::get_head()
  223. {
  224.     return Head;
  225. }
  226.  
  227. void find_memory(Heap* heap, LIST_SEGMENTS* List, int K, int query_number,
  228.     std::vector<int>& answers, list_segments** requests)
  229. {
  230.     int old_l;
  231.     heap_elements* heap_head;
  232.  
  233.     heap_head = heap->get_head();
  234.     if (!heap->isempty() & (heap_head->r - heap_head->l + 1) >= K)
  235.     {
  236.         if ((heap_head->r - heap_head->l + 1) == K)
  237.         {
  238.             heap_head->to_list->status = 0;
  239.             requests[query_number] = heap_head->to_list;
  240.             answers.push_back(heap_head->l);
  241.             heap->delete_vertex(0);
  242.         }
  243.         else
  244.         {
  245.             old_l = heap_head->l;
  246.             heap_head->l = old_l + K;
  247.             heap_head->to_list->l = old_l + K;
  248.  
  249.             if (heap_head->to_list->prev != NULL)
  250.             {
  251.                 List->add(old_l, old_l + K - 1, 0, -1, heap_head->to_list->prev);
  252.                 requests[query_number] = heap_head->to_list->prev;
  253.             }
  254.             else
  255.             {
  256.                 List->add_head(old_l, old_l + K - 1, 0, -1);
  257.                 requests[query_number] = List->get_head();
  258.             }
  259.  
  260.             heap->siftdown(0);
  261.             answers.push_back(old_l);
  262.         }
  263.     }
  264.     else
  265.     {
  266.         requests[query_number] = NULL;
  267.         answers.push_back(-1);
  268.     }
  269. }
  270.  
  271. void free_up_memory(Heap* heap, LIST_SEGMENTS* List, int q, int query_number,
  272.     std::vector<int>& answers, list_segments** requests)
  273. {
  274.  
  275.     if (requests[q] != NULL)
  276.     {
  277.         requests[q]->status = 1;
  278.         if (requests[q]->prev != NULL)
  279.         {
  280.             if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
  281.             {
  282.                 requests[q]->l = requests[q]->prev->l;
  283.                 heap->delete_vertex(requests[q]->prev->to_heap);
  284.                 List->delete_segment(requests[q]->prev);
  285.             }
  286.         }
  287.         if (requests[q]->next != NULL)
  288.         {
  289.             if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
  290.             {
  291.                 requests[q]->r = requests[q]->next->r;
  292.                 heap->delete_vertex(requests[q]->next->to_heap);
  293.                 List->delete_segment(requests[q]->next);
  294.             }
  295.         }
  296.  
  297.         heap->add(requests[q]->l, requests[q]->r, requests[q]);
  298.         requests[query_number] = requests[q];
  299.         requests[q] = NULL;
  300.     }
  301.     else
  302.     {
  303.         requests[query_number] = NULL;
  304.     }
  305. }
  306.  
  307.  
  308. int main()
  309. {
  310.  
  311.     int N, M, K, q;
  312.     int old_l;
  313.  
  314.     Heap heap;
  315.     LIST_SEGMENTS List;
  316.  
  317.     heap_elements* heap_head;
  318.     std::vector<int> answers;
  319.  
  320.     std::cin >> N;
  321.  
  322.     List.add_head(1, N, 1, 0);
  323.     heap.add(1, N, List.get_head());
  324.  
  325.     std::cin >> M;
  326.     list_segments* requests[M];
  327.  
  328.     for (int query_number = 0; query_number < M; ++query_number)
  329.     {
  330.         std::cin >> K;
  331.         if (K > 0)
  332.             find_memory(&heap, &List, K, query_number, answers, requests);
  333.         else
  334.         {
  335.             q = -K - 1;
  336.             free_up_memory(&heap, &List, q, query_number, answers, requests);
  337.         }
  338.     }
  339.  
  340.     for (int i = 0; i < answers.size(); ++i)
  341.         std::cout << answers[i] << std::endl;
  342.  
  343.     return 0;
  344. }
  345.  
RAW Paste Data