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

Автор starbot, история, 7 лет назад, По-английски

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 )

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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://mirror.codeforces.com/contest/86/status/D?order=BY_CONSUMED_TIME_ASC