Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math>
- #include <string>
- using namespace std;
- const MAX = 2e5;
- class Segment_Tree
- {
- int* tree;
- int tree_size;
- int count_numbers;
- std::vector<int> numbers;
- public:
- segment_tree();
- segment_tree(int count_numbers);
- };
- void Segment_Tree::build_tree(const std::vector<int>& numbers, int v, int tl, int tr)
- {
- if (tr - tl == 1)
- tree[v] = numbers[tl];
- else
- {
- int tm = (tl + tr) / 2;
- build (numbers, v*2+1, tl, tm);
- build (numbers, v*2+2, tm, tr);
- tree[v] = tree[v*2+1] + tree[v*2+2];
- }
- }
- int Segment_Tree::to_deg_of_two(std::vector<int>& numbers, int count_numbers)
- {
- int p = 1;
- while (count_numbers > p)
- p *= 2;
- for (int i =0; i < p-count_numbers; ++i)
- numbers.push_back(MAX);
- return 2*p;
- }
- Segment_Tree::Initialize(int count_numbers)
- {
- this->count_numbers = count_numbers;
- for (int i =1; i <= count_numbers; ++i)
- numbers.push_back(i);
- this->tree_size = to_deg_of_two(numbers, count_numbers);
- this->tree = new int[tree_size];
- build_tree(numbers, 0, 0, count_numbers);
- }
- Segment_Tree::get_min(int l, int r)
- {
- }
- Segment_Tree::find_spot(char start_number)
- {
- int start = stoi(start_number);
- int min_num = get_min(start, this->count_numbers-1);
- if (min_num == MAX)
- {
- min_num = get_min(0, start-1);
- if (min_num == MAX)
- return -1 :
- else
- {
- set(min_num-1,MAX);
- return min_num;
- }
- }
- else
- {
- set(min_num-1,MAX);
- return min_num;
- }
- }
- Segment_Tree::free_up(char number)
- {
- int num = stoi(number);
- if tree[num-1] == MAX
- {
- set(num-1,num);
- return 0;
- }
- else
- return -2;
- }
- int main()
- {
- int n,m;
- cin >> n >> m;
- Segment_Tree tree;
- tree.Initialize(n);
- string s[3];
- for (int i=0; i < m; ++i)
- {
- cin >> s;
- if (s[0] == "+")
- find_spot(s[3]);
- else
- free_up(s[3]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement