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

Need help with 446C
Автор NoTwo, история, 9 лет назад, По-английски

Hello,
I'm trying to solve 446C - DZY Loves Fibonacci Numbers and i can't debug my code. I'm simply using a segment tree to get the sums.I would really be happy if someone could tell me my mistakes.

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

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

I guess you misunderstood the problem, for each update you should do following from L to R: a[L] += f[L], a[L + 1] += f[L + 1] ... a[R] += f[R]

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    nope it says for each l <= i <= r: a[i] += f[i-l+1] thus a[l] += f[1], a[l+1] += f[2], ..., a[r] += f[r-l+1]

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Ok, the wrong part is you add pf[q — p — 1] to all a[i] from l to r

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        i tried pf[q-p] before, still wrong :(

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

          Yes, it must be wrong, you can not do updates correctly with this approach because every element doesn't get constant number and its correct solution isn't as simple as you think, try to look others code or tutorial to get the idea

          → Ответить