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

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

https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=8&category=804&page=show_problem&problem=6491

Hi, I am trying to solve this problem from ACM ACPC 2017 — Array Queries contest using segment tree + lazy propagation but always gets wrong answer no matter what. Am I missing something or is my approach wrong ?

Here is my code: https://ideone.com/3s2FQk

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

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

Additionally, I think that the way in which you make propagation is wrong, but if you fix those things probably you get TLE, because the first operation is in the worst case O(N)

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

Why bother with segment trees? There is a simple O(N3log2(N)) solution using Adolf's Red-Black-Yellow tree.