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://mirror.codeforces.com/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 )
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*xis equivalent toans += (2*c+1)*x, c++, and similarly for subtraction.You can get some more ideas by looking at the fastest submissions here: http://mirror.codeforces.com/contest/86/status/D?order=BY_CONSUMED_TIME_ASC
Thanks a lot.
Edit:- time reduced from 4900ms to 2400ms !!!