I search it in google , but i can't find it. Can somebody tell me how to use lower_bound in set<pair<int,int>> , so i can find the fist pair whose first element is not small than the element i search for ?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 02:52:41 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
x.lower_bound({first, -inf});got it! Thanks.
Could you explain the reasoning behind using that ? Also could you tell how you would do it for upper_bound ? Thanks :)
x.upper_bound({first, inf});
In these implementations we only care about the first value.
pair<int,int> will compare the first int first, then the second int. We want ALL second integers to work
As for upperbound Na2a uses {first, inf} because we want the value to be greater than first, and {first, inf} is the highest pair with first as its first value. (again, we only care about the first value)
How to get the index of that pair,i mean we can't do this:x.lower_bound({first,-inf})-x.begin()?
There is no way to do that, set can't get index of key. You can use this though http://codeforces.net/blog/entry/11080
This is a pretty good site : http://bit.ly/1DMMnub
I didn't knew such site exists!
Wow , Awesome site .
Wow , Awesome necro .
Your link actually gives us the link of this blog -
Well, there is actually an answer on that page!
Recursion ...
error:stack overflow,no base case
How can i call lower_bound on pair<int,int> to get the last occurence of pair if element is repeating ?
For eg :
[7,1,5,3,1,1]
[ {1,1,} , {1,4} , {1,5}, {3,3}, {5,2}, {7,0} ]
if i do lower_bound for should get pair {1,5}
try auto it = st. upper_bound({first+1,-inf})
if(it == st.begin()) element not found
else element in it--
can u explain more ?
upper bound return an iterator that points to the first element strictly bigger than {x,y}
st. upper_bound({first+1,-inf}) return an iterator to the first element strictly bigger than the element we are looking for
for example :
[ {1,1,} , {1,4} , {1,5}, {3,3}, {5,2}, {7,0} ]
auto it = st. upper_bound({2,-inf})
*it = {3,3}
so to get {1,5} all we need to do is it--;
A corner case is :
[ {3,3}, {5,2}, {7,0} ]
auto it = st. upper_bound({2,-inf})
*it = {3,3} (it = st.begin())
in this case it-- is not defined so this will cause a runtime error
tha's why we need to test if (it == st.begin())
PS : in our case lower_bound will give the same result as we are sure that no pair have the second element equals -inf so stricly bigger ( < ) or stricly bigger or equal ( <= ) gives the same result
you can do it this way : s.lower_bound(make_pair(x, y)) or s.lower_bound(pair(x, y)). (the last case just in c++17).