The explanation using multiset was written in the E problem of AtCoder Beginner Contest, but I think that there are languages such as python that do not have mutiset, so I would like to introduce an alternative algorithm using Priority Queue (heapq). I will not explain the problem itself, so please read the official explanation there.
ABC170 E - Smart Infants https://atcoder.jp/contests/abc170/tasks/abc170_e
multiset Internally [Binary Search Tree](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C % A8) is used. This keeps the data sorted at all times instead of taking O (logN) every time a data is inserted. Therefore, it is possible to delete and search with O (logN). By implementing the binary search tree yourself, you can use it in languages that are not provided as standard, but you need to devise to maintain the balance. (Example of ingenuity: [Tree master training course] 7-1. What is Splay tree? Explanation [Competition professional Katsuppa])
Priority Queue Internally in GCC [binary heap](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83 % 97) is used. The same data structure is used internally in python's heapq. Inserting data takes O (logN) every time, like a binary search tree. Since it is a heap tree, the inside is ** not sorted, and you cannot search or delete anything other than the maximum (minimum) value at high speed **, but you cannot always get the maximum (minimum) value with the computational complexity O (1). I can do it. The advantage over the binary search tree is that the amount of calculation is stable because the equilibrium is always maintained without any special effort.
In this issue
It would be nice if could always be done at high speed.
As mentioned in the official commentary, each process can be performed at high speed by using multiset, but since the 4th process cannot be performed at high speed with Priority Queue, it is necessary to change the way of thinking.
In solving this problem, let's note that the fourth condition is ** not necessarily a process that must be performed unless it interferes with the first and second conditions **. In other words, it doesn't matter if the maximum value of the rate set and the minimum value of the maximum rate set in each kindergarten are not affected even if they are not actually deleted from the data.
Since the implementation does not change under the first and second conditions (the maximum and minimum are flipped over), the first condition (obtaining the maximum value of the set) will be explained as an example.
Now consider having two Priority Queues.
And ** insert an element in 1 when you enter the park and in 2 when you change the park. If the maximums of 1 and 2 are the same, remove them from both. ** ** This ensures that the maximum value for this kindergarten is always the same as the maximum value for 1.
I'll put some code here, but it doesn't work even if I copy it depending on the environment because std and include are broken.
code.cpp
priority_queue<int> in;
priority_queue<int> out;
//Processing when entering the park
void infant_in(int i){
in.push(i);
}
//Processing when changing gardens
void infant_out(int i){
out.push(i);
while(!out.empty() && in.top() == out.top()){
in.pop();
out.pop();
}
}
//Get maximum
int get_max(){
return in.top();
}
Let's look at a concrete example. Consider that kindergartens with rates of 3, 5 and 8 enter the kindergarten, and then children with rates of 5 and 8 move in this order.
>Three kindergarten children enter
Actual kindergarten= {3,5,8}
1 = [3,5,8] 2 = [] #Of course the maximum value at this point is 8
>Children with a rate of 5 are transferred
Actual kindergarten= {3,8}
1 = [3,5,8] 2 = [5] #The maximum value is 8
>Children with a rate of 8 are transferred
Actual kindergarten= {3}
1 = [3,5,8] 2 = [5,8]
1 = [3,5] 2 = [5]
1 = [3] 2 = [] #The maximum value is 3
With this kind of feeling, you can see that there is no problem in getting the maximum value.
It is an interesting calculation amount, but since the number of times to delete the value from in and out that seems to be a bottleneck in this problem is Q times at the maximum, it can be ignored, and the calculation amount is O (NlogN) required when inserting the value. Become. This is fast enough.
Recommended Posts