Блог пользователя coco_elon

How do I optimize my Mo's algorithm solution?
Автор coco_elon, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I believe this should be enough

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить