By Warhead38, history, 5 weeks ago, ,

problem link:https://www.spoj.com/problems/XXXXXXXX/ solution link:https://ideone.com/gh52Zm TLE after 20th test case at spoj. plz help someone.

• -8

 » 5 weeks ago, # |   -8 Your code is quite hard to read and understand. When you're asking for help, even a small bit of commentary would go a long way.That said, the comments on the website are clear MO with update + compression = AC Try using compression on the stored numbers so you don't need slow accesses to the unordered_map f. Instead it can be replaced by an array that stores the value of each used number.
•  » » 5 weeks ago, # ^ |   -8 but by using array i wont be able to check the count of -ve numbers. also i dont know about compression.
•  » » » 5 weeks ago, # ^ |   +1 So, you read the original array and all the queries to start with.Take each value that will ever be in the array (both to start or afterwards) and put it into a vector> where the first is the number and the second is a pointer back to it. call it compress.Run sort() on that array.Also make an array to hold your mapping back to the original numbers. call it orig. Now do something like follows: int curr = compress[0].first; int idx = 0; for(int i = 0; i < compress.size(); i++) { if(curr != compress[i].first) idx++; curr = compress[i].first; orig[idx] = curr; *compress[i].second = idx; } Now you're guaranteed that each number you might store has a unique id < orig.size(), and you can recover the original value by reading it from orig. Now that all the numbers you're working with are small, you can turn f from a slow map into a fast array. Just remember that instead of cnt += ele, to do cnt += orig[ele] instead.
•  » » » » 5 weeks ago, # ^ |   -8 ok i will try this and tell you. thanks a lot
•  » » » » 5 weeks ago, # ^ |   -8 1 thing more what do you mean by storing that value which will ever be in array.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 So you have the starting values (1 2 4 2 3 in the example) and the ones that are placed later by U queries (such as 7)
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 wait
•  » » » » » » 5 weeks ago, # ^ |   -8 not giving correct answer now on sample testcase: solution: https://ideone.com/GkpgV4
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 You need to use the compressed versions everywhere besides calculating your cnt. I see that you use non-compressed numbers in pvh and upd (you copy the numbers there before compression)
•  » » » » » » » » 5 weeks ago, # ^ |   0 solution:https://ideone.com/OtbP1g not correct answer on sample. can you do the changes in it?
•  » » » » » » » » 5 weeks ago, # ^ |   0 ?