### anajin's blog

By anajin, 6 years ago,

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 ?

• +3

 » 6 years ago, # |   +35 x.lower_bound({first, -inf});
•  » » 6 years ago, # ^ |   0 got it! Thanks.
•  » » 6 years ago, # ^ |   0 Could you explain the reasoning behind using that ? Also could you tell how you would do it for upper_bound ? Thanks :)
•  » » » 6 years ago, # ^ |   0 x.upper_bound({first, inf});
•  » » » 3 years ago, # ^ |   0 In these implementations we only care about the first value.pair will compare the first int first, then the second int. We want ALL second integers to workAs 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)
•  » » 3 years ago, # ^ |   0 How to get the index of that pair,i mean we can't do this:x.lower_bound({first,-inf})-x.begin()?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +9 There is no way to do that, set can't get index of key. You can use this though http://codeforces.com/blog/entry/11080
•  » » 19 months ago, # ^ | ← Rev. 2 →   -48 ok
•  » » 19 months ago, # ^ |   -23 IS INF IS INT_MAX???
•  » » » 19 months ago, # ^ |   0 INF is I think just a variable name, and its usually 1e18 , also you need to use long long to initialize it.
•  » » 10 months ago, # ^ |   0 really ?
 » 6 years ago, # |   -18 This is a pretty good site : http://bit.ly/1DMMnub
•  » » 6 years ago, # ^ |   0 I didn't knew such site exists!
•  » » 3 years ago, # ^ |   -13 Wow , Awesome site .
•  » » » 3 years ago, # ^ |   +15 Wow , Awesome necro .
•  » » 3 years ago, # ^ |   +53 Your link actually gives us the link of this blog -
•  » » » 3 years ago, # ^ |   +42 Well, there is actually an answer on that page!
•  » » » » 3 years ago, # ^ |   +20 Recursion ...
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   -26 error:stack overflow,no base case
 » 10 months ago, # |   0 How can i call lower_bound on pair 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}
•  » » 10 months ago, # ^ | ← Rev. 2 →   +11 try auto it = st. upper_bound({first+1,-inf}) if(it == st.begin()) element not found else element in it--
•  » » » 10 months ago, # ^ |   0 can u explain more ?
•  » » » » 10 months ago, # ^ |   0 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
 » 10 months ago, # |   -13 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).