Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

svg_af's blog

Problem with MO's algorithm
By svg_af, history, 11 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

»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
← 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
  • »
    »
    11 years ago, hide # ^ |
     
    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