I have been trying BOOKLIST http://opc.iarcs.org.in/index.php/problems/BOOKLIST question for a while but i am only able to fetch 60 points. I am using vectors to insert and erase elements. But because of complexity of erase,O(N), I am getting TLE. Can someone point me in the right direction. Is their some standard algorithm to solve these types of questions??
Here is my code: http://ideone.com/DVv5CN
seems like segment tree will be used
The hint i would suggest for this problem would be to think about sorting the set of book already issued.Here is the link to solved problem:http://ideone.com/zjshg7
ask me if any further doubts arises.
Great!! It works…
Logic is clear too…
i was also thinking about using segment trees but got lost. Do you have some idea?
each node stores the number of books that are not yet borrowed in the segment.