This is Dynamic BD problem. What structers are used? I used set<pair(money,numer)>(red-black tree) and finding,deleteng and inserting of data on each milliarders going, but of course there is more effective solution.
Thank for your Reply. Yeah, I used scanf/printf for IO. I think I should have reduce the number of maps in my code. I used following structures: map < string , int > city_to_index ;// locate the position of each city in the heap. map < string , string > where;// locate the city in where the billionaire is map < string , LL > how_much;// the amount of money each billionaire has map < string , int > answer;// the answers Do you have any idea to reduce them? One problem that I think that my cause TLE is that I built my heap in array and each time I update my heap I should have change the values in city_to_index. Maybe if I implement it with pointers would be better. I mean, it may be better to build the heap with pointers and for swapping the nodes their addresses in city_to_index remains unchanged. (map<string,node*> city_to_index) IT IS SOMEHOW COMPLICATED FOR ME TO IMPLEMENT IN THAT WAY, DO YOU HAVE ANOTHER IDEA?
Thanks for your advice. I had though about them before implementing my solution. and I think my running time except the part dealing with maps is O(lg n) per line of input and it is perfectly OK, and that's why I asked in forum about how to get rid of TLE.