NEERAJ2003's blog

Help in this segment tree question
By NEERAJ2003, history, 12 months ago, In English

Question is: https://www.codechef.com/problems/BOMBING?tab=statement submission: https://www.codechef.com/viewsolution/1035044414 approach I was thinking solving with pref of array and (segment tree) that is counting the current open system and minus with count of all system having end less me and start greater than me and as element can be equal iam only updating there first occurrence count that resolve the things but still not accepting anyone can tell what the issue along with anyone similar question on codeforces. ( similar to codeforces 61E (https://mirror.codeforces.com/problemset/problem/61/e )

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
12 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

You can use a lazy sparse segment tree.

When adding a system with range [l, r] add 1 to all houses in the given range. When moving a system with range [l, r], first substract 1 from all houses in the range then add 1 to houses in range [l+d, r+d].

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

    I want to solve without lazy propagation as the above approach convert question to point update and range query therefore the above approach also should work and my friend debug it and what Iam doing wrong is that while taking the previous query for update the range I was taking that from array "a" but that contain the sequence of all kinds of query not the available defenses range.
    submission: https://www.codechef.com/viewsolution/1035095291

    → Reply