I have understood the sqrt decomposition + SOS DP approach to the problem. This is an accepted solution to the problem. However, on changing the size of the array Q_MAX to 'N_MAX + 100', I am getting WA. Why is that?
Changing the constant Q_MAX (that represents the quantity of queries = 2**18) to N_MAX (that represents the total of monsters = 2**17), you are decreasing the array size in (2**18)-(2**17), that is, obviously, greater than 100.
Changing the constant Q_MAX (that represents the quantity of queries = 2**18) to N_MAX (that represents the total of monsters = 2**17), you are decreasing the array size in (2**18)-(2**17), that is, obviously, greater than 100.
Can you provide the Time Complexity of your solution?
See this