Hello everyone. For the May Long Contest’s problem MSTICK, I came out with a python solution which is as fast as the AC ones I checked when the contest ended. However, my solution got TLE. Can someone tell me what’s wrong with it ? Here is the code. Thank you, I’m working on it for weeks now ! I even learned to implement a segment tree but it is still slow.
append() can cause python to allocate more memory, which takes time. By using pre-allocated structure, time is saved in performing all the individual allocations.
2 Likes
Well ! i think i found a drawback to your method. 
When the input is sorted, your precalculation loops are in O(n^2).
Take this input :
100000
1 2 3 4 5 6 [...] 99999 100000
1
0 0
I think the loops are far too expensive.
1 Like
Thank you for your answer. Even if it didn’t AC my solution, it improved it.
1 Like
-
For taking input you can use “x,y = map(data type, raw_input().split)”
-
You can implement sparse table as cyberax suggested.
Ah ok thanks ! I’ll try the sparse table. However it bothers me to not understand why my code doesn’t AC whereas it is faster (on my machine with the max input) than your solution. Of course, I don’t pretend it is better, I just wanted to understand that abnormality.
ok, i’ll have a look at it. i’ll tell you if i find out 
Oh thanks ! I tried it and you’re absolutely true. Finally I understand my mistake now. I also implemented a segment tree that runs in 20 seconds, will try your method ASAP