svg_af's blog

Problem with MO's algorithm
By svg_af, history, 9 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

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

    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

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

      I got TLE as well initially. Try coordinate compression because it got me AC finally.

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

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

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

    The little things that one should be careful of

    Thank you for pointing that out

    → Reply