coco_elon's blog

How do I optimize my Mo's algorithm solution?
By coco_elon, history, 8 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

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

I believe this should be enough

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the quick response! But it still does not pass.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Actually I submitted it and got AC. Maybe you submitted something wrong.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks, it passed. But this solution is exactly the same: http://ideone.com/kKKV97

        Why is it so slow?

        EDIT: Found the mistake. Thanks for the quick help!

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Well, in MO's algorithm, usually, every bucket shoud be sorted in ascending order by R. Your comparator does not guarantee that.

          → Reply
»
8 years ago, # |
  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
»
8 years ago, # |
  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