ibrahimsherif's blog

By ibrahimsherif, history, 5 weeks 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

 
 
 
 

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

According to uHunt this problem hasn't propper judge input and consequently any submission should give WA.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But according to live archive there was successful submissions.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sometimes they do not close not-yet-ready problems and anyone can submit to it and even get AC. But it's better not to do it. The problem will be rejudged when the judge input will be ready.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you my friend. How you can tell from uhunt if any problem doesnt have proper input for further problems ?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For such problems the numbers are strikethrough. There are many of them :(

»
5 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is the propagation wrong if you can elaborate more because i tested it with multiple cases ? And if does get TLE how to optimize it ?

»
5 weeks 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.