vadimk772336

Untitled

Dec 8th, 2021
991
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int MAX = 2e5;
  7.  
  8. struct vertex
  9. {
  10.     int res;
  11.     int left;
  12.     int right;
  13. };
  14.  
  15. class Segment_Tree
  16. {
  17.     struct vertex* tree;
  18.     int tree_size;
  19.     int count_numbers;
  20.     std::vector<int> numbers;
  21.  
  22. public:
  23.     void build_tree(const std::vector<int>& numbers, int v, int tl, int tr);
  24.     int to_deg_of_two(std::vector<int>& numbers, int count_numbers);
  25.     void Initialize(int count_numbers);
  26.     void set(int k, int x);
  27.     int get_min(int node, int a, int b);
  28.     int find_spot(char* start_number);
  29.     int free_up(char* number);
  30. };
  31.  
  32. void Segment_Tree::build_tree(const std::vector<int>& numbers, int v, int tl, int tr)
  33. {
  34.  
  35.     if (tr - tl == 1)
  36.     {
  37.         tree[v].res = numbers[tl];
  38.         tree[v].left = tl;
  39.         tree[v].right = tr;
  40.     }
  41.     else
  42.     {
  43.         int tm = (tl + tr) / 2;
  44.         build_tree(numbers, v * 2 + 1, tl, tm);
  45.         build_tree(numbers, v * 2 + 2, tm, tr);
  46.         tree[v].left = tl;
  47.         tree[v].right = tr;
  48.  
  49.         if (tree[v * 2 + 1].res < tree[v * 2 + 2].res)
  50.             tree[v].res = tree[v * 2 + 1].res;
  51.         else
  52.             tree[v].res = tree[v * 2 + 2].res;
  53.     }
  54. }
  55.  
  56. int Segment_Tree::to_deg_of_two(std::vector<int>& numbers, int count_numbers)
  57. {
  58.  
  59.     int p = 1;
  60.     while (count_numbers > p)
  61.         p *= 2;
  62.  
  63.     for (int i = 0; i < p - count_numbers; ++i)
  64.         numbers.push_back(MAX);
  65.  
  66.     return 2 * p;
  67. }
  68.  
  69. void Segment_Tree::Initialize(int count_numbers)
  70. {
  71.  
  72.     this->count_numbers = count_numbers;
  73.     for (int i = 1; i <= count_numbers; ++i)
  74.         numbers.push_back(i);
  75.  
  76.     this->tree_size = to_deg_of_two(numbers, count_numbers);
  77.     this->tree = new vertex[tree_size];
  78.     build_tree(numbers, 0, 0, count_numbers);
  79. }
  80.  
  81.  
  82. void Segment_Tree::set(int k, int x)
  83. {
  84.     int v = tree_size - 1 + k;
  85.     tree[v].res = x;
  86.     while (v > 0)
  87.     {
  88.         v = (v - 1) / 2;
  89.  
  90.         int l_min = tree[2 * v + 1].res;
  91.         int r_min = tree[2 * v + 2].res;
  92.         (l_min < r_min) ? tree[v].res = l_min : tree[v].res = r_min;
  93.     }
  94. }
  95.  
  96. int Segment_Tree::get_min(int node, int a, int b)
  97. {
  98.     int l = tree[node].left;
  99.     int r = tree[node].right;
  100.     if (r <= a || l >= b)
  101.         return MAX;
  102.  
  103.     if (r < b & l >= a)
  104.         return tree[node].res;
  105.  
  106.     int m1 = get_min(node * 2 + 1, a, b);
  107.     int m2 = get_min(node * 2 + 2, a, b);
  108.     return (m1 < m2) ? m1 : m2;
  109. }
  110.  
  111. int Segment_Tree::find_spot(char* start_number)
  112. {
  113.  
  114.     int start = stoi(start_number);
  115.     int min_num = get_min(0, start, this->count_numbers - 1);
  116.  
  117.     if (min_num == MAX)
  118.     {
  119.         min_num = get_min(0, 0, start - 1);
  120.  
  121.         if (min_num == MAX)
  122.             return -1;
  123.         else
  124.         {
  125.             set(min_num - 1, MAX);
  126.             return min_num;
  127.         }
  128.     }
  129.  
  130.     else
  131.     {
  132.         set(min_num - 1, MAX);
  133.         return min_num;
  134.     }
  135. }
  136.  
  137. int Segment_Tree::free_up(char* number)
  138. {
  139.     int num = stoi(number);
  140.  
  141.     if (tree[num - 1].res == MAX)
  142.     {
  143.         set(num - 1, num);
  144.         return 0;
  145.     }
  146.     else
  147.         return -2;
  148. }
  149.  
  150. int main()
  151. {
  152.  
  153.     int n, m;
  154.     cin >> n >> m;
  155.  
  156.     Segment_Tree tree;
  157.     tree.Initialize(n);
  158.  
  159.     string s;
  160.     for (int i = 0; i < m; ++i)
  161.     {
  162.         cin >> s;
  163.         if (s[0] == '+')
  164.             tree.find_spot(&s[3]);
  165.         else
  166.             tree.free_up(&s[3]);
  167.     }
  168.  
  169.     return 0;
  170. }
  171.  
RAW Paste Data