SPOJ-DQUERY TLE with MO's Algorithm

general
, ,
1

Here’s the question [DQUERY][1].
I’m using MO’s Algorithm and here’s my


[2]. Tried almost everything. fast i/o,print scanf,all other optimizations.

Any help please?
Thanks in advance. :)


  [1]: http://www.spoj.com/problems/DQUERY/
  [2]: http://ideone.com/b2ARA3
1 Like
2

You can refer to my solution at http://ideone.com/91Uwc4

It passes without using fast io.

I think your solution is giving tle because of the compare function. Firstly, your 2nd return statement is wrong, as we just return on basis of “r” values and not on basis of “r/block_size” value. Second, we are doing the same calculation for “l/block_size” 4 times, where it can be done only 2 times using variable. (See my compare function). So the contant factor reduces in your code too. Hope this would do the job.

5 Likes
3

Thanks for the feedback. I was getting TLE because of using vector of nested pair. By using structure got AC. Thanks for your response. :slight_smile:

4

If you feel your question was answered, mark it as accepted.

5

Here is my solution using Fast I/O