The repository that contains all solutions made for the course Competitive Programming and Contests by the University of Pisa

View the Project on GitHub

Frogs and mosquitoes

Solved Solution Time :clock11:
:heavy_check_mark: Segment Tree 1200 ms

Solution or Solution discussion

Segment Tree solution

To get_position_close_frog this problem is possible use the Segment Tree data structure, without Lazy Propagation for the motivation wrote in the paper Segment Tree: A Complete Introduction by Examples.

The basic idea is to use the Segment Tree to store the data of the frogs, like pos + length tongue, if the frog exist is possible use a binary search to get the index of this frog, and after that we can make all operation where a frog can eat a mosquito. However, if there is any frog at the moment that can eat the mosquito, is possible store the mosquito in a multiset (because can be duplicate in position) and maintain the mosquito that can not eat from any frog in this multiset and check if one of these mosquito can be eaten from a frog with the new dimension of the tongue.

The Segment tree contains only the position of the frogs sorted by position.

The time complexity of the algorithm is O((n + m)log(n + m)).