starbot's blog

Problem on MO's algo
By starbot, history, 7 years ago, In English

My solution to the problem barely passed after many optimizations.... This problem mainly asks to calculate a function's value over a range of array and give output. My solutions uses a offline query method.(MO's algorithm) Can anyone suggest any improvements !!

Problem : http://codeforces.net/problemset/problem/86/D

My Solution's Link : https://pastebin.com/Gcuxet5h

Thank You !

(PS : any other ways to do the problem are also welcomed :D )

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

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I was struggling with that same problem recently. The biggest improvement I achieved was by reducing the number of arithmetic operations inside the four while loops that move the interval ends around.

In this specific case, note that ans -= c*c*x, c++, ans += c*c*x is equivalent to ans += (2*c+1)*x, c++, and similarly for subtraction.

You can get some more ideas by looking at the fastest submissions here: http://codeforces.net/contest/86/status/D?order=BY_CONSUMED_TIME_ASC

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

    Thanks a lot.

    Edit:- time reduced from 4900ms to 2400ms !!!

    → Reply