When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ibrahimsherif's blog

By ibrahimsherif, history, 5 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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