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
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:04:04
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:04:04
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 23:30:56 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
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://codeforces.net/contest/1843/submission/210506220
Also I didn't quite get wym by " check there at least on segment available " ??
thanks man got it :)
you don't need segment trees for this... its just a basic binary search
Why learning segment trees when you haven't even solved 1300-Rated problems ?
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...
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
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.
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.