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

Horrible Queries
Автор pikkupr, 10 лет назад, По-английски 
Hello everyone!! this is my first time trying Lazy updates and i\'m getting incorrect results for problem http://www.spoj.com/problems/HORRIBLE/ .
output of test cases through my code:
80
408
though correct output is
80
508

here is my code : http://ideone.com/Yb0ZVO

thanks a lot!
  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

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

use http://paste.ubuntu.com :Dubuntu pastebin

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

Is this link broken ?? http://ideone.com/Yb0ZVO

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

line 78-81 in update function

if(rj<=mid)
    return update(l,i,mid,ri,rj,v);
if(ri>mid)
    return update(l+1,mid+1,j,ri,rj,v);

deleted,

write

if(j<ri || i>rj)
     return segtree[t].sum;

my english cant enough for explain

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

    By doing this test cases passed. But, On spoj it is giving runtime error (SIGSEGV) :(

    and can you explain the reason for doing so??

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

      ur segtree size is too small need to be 4*N so take segtree[100005*4] , and watch long long int

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

http://paste.ubuntu.com/8420003/

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

    your code is not passing the updated values to child nodes neither in update nor in query function. So, can you explain?

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

      His code actually does except it is not clear. I ran it on my machine and it seems to work fine. However, I do not recommend such a implementation as it lacks clarity in the propagation. My implementation is as follows:

      http://ideone.com/WA9fS8

      My down method is where I pass the updated values to the next child nodes.

      Hope this helps

      → Ответить