Parazit's blog

please help me in this segment tree with lazy updates problem!!
By Parazit, history, 8 years ago, In English

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2397 it is a level 4 problem in uva online judge about segment tree.i used segment tree with lazy updates but i got time limit for 20 times!can any one help me?does this problem have some particular tip?

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Parazit (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you show your code? I think your solution is OK, maybe you have a bug.
Also I think that slow data input method and the strange way of receiving the input string can be faulty here.

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

    http://paste.ubuntu.com/18189099/

    Here is my code.I will become so glad if you can debug it.It is making me crazy!excuse me for my bad indent.

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

      Your solve() function seems to be wrong and slow...
      And I don't quite understand your implementation :(
      One of the most obvious buggy parts: lines 67-75. It seems that you want to reset mark[ras] to zero, but you actually never do it, since one of the ifs before mark[ras] = 0 will call a return.
      It's really hard for me to debug your code, so the best thing I can probably do is coding the problem in my own style and providing you the code, if you want.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thank you very much for reading my code!

        please do its coding in your own style for me if you can.

        thank you very very very much!!

        → Reply