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

Problem with MO's algorithm
Автор svg_af, история, 9 лет назад, По-английски

Hello there I've been reading up on MO's algorithm and sqrt decomposition and i think i've figured out the concept

so i'm trying to solve this problem but i keep getting TLE and i can't seem to figure out what i'm doing wrong

Here's my code

Thank you all in advance :D

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Change some strings:

this->bucket = ord/bsize on this->bucket = l/bsize

if (q1.bucket!=q2.bucket) return q1.r<q2.r; on if (q1.bucket==q2.bucket) return q1.r<q2.r;

Now it passed 49 tests instead of 5 14994457 Maybe there are some another bugs.

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

    well what you said plus using int instead of long long all over except for the results got me an Accepted :D thank you so much man

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

As multiplication is costly operation, instead of using (t*t-(t-1)*(t-1)) replace by (2*t — 1) I got AC

15606787

and the changes given by komendart

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

    The little things that one should be careful of

    Thank you for pointing that out

    → Ответить