vikas11111's blog

help on segment tree
By vikas11111, history, 17 months ago, In English

I wants to do this question with segment tree
i know i can change element in logn time but how i can check there at least on segment available or not according to the que

que link link

plz help

  • Vote: I like it
  • -6
  • Vote: I do not like it

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

In the contest, I tried implementing the Segment tree and thought the prefix array won't pass the time constraints, but I was wrong, here is my segment tree AC solution although it can be further optimized.

https://mirror.codeforces.com/contest/1843/submission/210506220

Also I didn't quite get wym by " check there at least on segment available " ??

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

you don't need segment trees for this... its just a basic binary search

→ Reply
»
17 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Why learning segment trees when you haven't even solved 1300-Rated problems ?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yeah, In last maybe 20 rounds i dont see a problem(with rating <= 2000), which have solution like "segment tree" or simething more harder. But learning it when you are 1000...

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

If you're curious, this is a working solution with binary search and prefix sums — no segtree needed, and takes only ~60ms and 1.5MB: 210537397

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why do you learn Segment Tree? Go learn Binary Search.

In fact Binary Search was the expected solution, stop overcomplicating your solutions using hard algorirthms.

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

If you are interested in the range update method of solving the problem but you need an easy way to do this, I recommend the square root algorithm. It's more suited for beginners, and it is what I used in the contest.

→ Reply