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

please help me in this segment tree with lazy updates problem!!
Автор Parazit, история, 8 лет назад, По-английски

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?

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

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

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить