coco_elon's blog

How do I optimize my Mo's algorithm solution?
By coco_elon, history, 9 years ago, In English

This is my solution for 86D : Powerful Array. Link: http://ideone.com/618TcS

This gave me a TLE at test 6, taking more than 5000 ms whereas most AC solutions pass at 800 — 1000 ms. How do I optimize my code? Thanks in advance!

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I believe this should be enough

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I am having the same problem. I submitted using MO's Square Root Decomposition, it gave TLE on 6 testcase. My submission.

→ Reply
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Use this cmp to sort queries:

bool cmp(Query a, Query b){
    if(a.left / sq != b.left / sq)
        return a.left < b.left;
    return a.left / sq % 2 ? a.right < b.right : a.right > b.right;
}

This would be helpful.

→ Reply