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

Help in this segment tree question
Автор NEERAJ2003, история, 11 месяцев назад, По-английски

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://codeforces.net/problemset/problem/61/e )

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

»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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].

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

    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

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

just segment ur treee

→ Ответить