pikkupr's blog

Horrible Queries
By pikkupr, 10 years ago, In English 
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!
  • Vote: I like it
  • -17
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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

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

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

    and can you explain the reason for doing so??

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

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

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

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

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

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

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

      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

      → Reply