Iarcs BOOKLIST problem

general
, ,
1

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

Thanks.

1 Like
2

seems like segment tree will be used

3

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.

1 Like
4

Great!! It works…
Logic is clear too…
Thanks&&Cheers

5

i was also thinking about using segment trees but got lost. Do you have some idea?

6

each node stores the number of books that are not yet borrowed in the segment.