I learned segment tree yesterday and tried to solve these following problems
399D - Красим стену
61E - Противник слаб
459D - Задача Пашмака и Пармиды
My solutions just barely pass the time limit.
81038127
81106193
81148972(needed faster I/O)
How can I strengthen this segment tree so that my solution fits into time limit completely.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 162 |
| 3 | adamant | 161 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 6 | nor | 150 |
| 7 | atcoder_official | 147 |
| 7 | SecondThread | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.07.2024 00:06:31 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
I think array is faster than vector when the constraint is large. Also, long long is unnecessary, using int instead of long long reduces the execution time.
74662995
My submission for the first problem is just 300ms.
Wow, thanks bro.
From where you have learnt segment tree ?
From everywhere, youtube gives theory, GFG gives some idea of code, then try questions on Codeforces.
First of all, segment tree is not essential in your position. Cause it would look hard for you in the green region. I suggest learning segment tree after crossing 1500. What you need right now is to get good enough to solve implementation problems and logic building for div3 C, D and div2 C. Maybe you can learn binary search and stl. Believe me, doing segment tree are not going to be helpful right now.
Once you are comfortable with the implementation and logic building problems, then move on for algorithms.
And you can learn segment tree from here if you desperately want. https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/
The competitive programmers handbook covers it nicely: https://cses.fi/book/book.pdf
Your segtree is fine, just use
ios_base::sync_with_stdio(false). People should stop misleading other people that arrays are faster than vectors, most of the times they are not.I prefer vectors over arrays, however I would say that multi-dimensional arrays are better than multi-dimensional vectors, for example a 2D matrix where I do operations row-wise: arrays would have a great cache locality whereas in vector since the next row is at a different location you would have cache misses for all rows (though the difference would only be apparent when you are really trying to fit your slow algo in the TL xD).
"in vector since the next row is at a different location", any sources about this?
Ummm.... The only way I know to make a multi-dimensional vector is to use
vector<vector<T>> vec(n, vector<T>(m)), and it is obvious that here the row vectors are all constructed seperately so each of them would have a different memory location.Fair point. I agree that when we start thinking about multidimensional arrays, things start to change. However, for 1D arrays I've never seen notable difference (at least, as long as you're preallocating the vector size instead of using
push_backoremplace_back).However, there's also an upside to this. Address sanitizer can catch out-of-bounds errors on 2D
vectors, and not on matrices (feel free to correct me if this is not the case).For 1D preallocated vectors, yes, I have never seen a difference. Infact, if we go by stackoverflow, there is no difference at all.
You are right about Address Sanitizer not catching it, but UBSan (
-fsanitize=undefined) does.