NoTwo's blog

Need help with 446C
By NoTwo, history, 9 years ago, In English

Hello,
I'm trying to solve 446C - DZY любит числа Фибоначчи 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.

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

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it +3 Vote: I do not like it

          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

          → Reply