By AHMADUL, history, 8 months ago,

I was trying to solve problem B1 of Helvetic Coding Contest 2019 online mirror (teams allowed, unrated). I got WA and TLE for a several time.Then I went to standings and found a line from a submission: int f=lower_bound(dg,dg+b,make_pair(a[i],10000000))-dg;
But,I couldn't understand it,,why I have to subtract dg at last??? Now, I am badly in need of help.Someone please explain the above statement.

• -9

 » 8 months ago, # |   0 lower bound returns first iterator of the value greater then or equal you are searching for. And by seeing your code it can be assumed it is used for finding the position of the value of make_pair(a[i], 10000000) in a container named dg. If you subtract dg from the returned iterator of lower_bound function then you will get the position. because dg is similar to dg.begin() here. both of them points first value of the container. [ extra tip: subtracting two iterator or pointer gives how many chunks of memory address are there between(not depends on your datatype) ]. you can know more about lower bound in here btw, next time please attach the code where you have taken a part from it. Cause now I don't know whether the dg container is sorted or not. or which container is it. Thanks, have a good day. :D
•  » » 8 months ago, # ^ | ← Rev. 3 →   -7 dg is an array(not std::array but std::pair dg[10]) but not a container. array shall not support begin() method, anyway it's not an obeject at all. and a container's name is also not equal to its begin() method. But since c++11 you can use std::begin() and std::end() whether arr is an array or a container.
•  » » » 8 months ago, # ^ |   0 coyorkdow i didn't know without a container we can store pairs. It would be nice of you if you give some reference about this. Thanks. :)
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +3 In c++ containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like vector, queues, lists and stacks. reference from https://en.cppreference.com/w/cpp/container. So std::pair is not a container but std::vector> is a container that stores std::pair. Meanwhile std::pair[100] and new std::pair[100] can also stores pairs but neither are container. When memory are allocated, each object will call its default constructor.
•  » » » » » 8 months ago, # ^ |   0 wow! didn't know about std::pairdg[b]. This explains everything! ^_^
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 Thank you,,,mamuuu.
 » 8 months ago, # | ← Rev. 2 →   +3 lower_bound returns an iterator(or an pointer if parameters are not iterators) pointing to the first element in the range [first, last) that is not less than value you gived. So if you want to get the index of an element then you should transform it into an integer. Both random iterator and or pointer support subtract operation and will return the numbers of differences of elements between two interators or pointers(i.e. an iterator pointing to a[5] subtract to an interator pointing to a[2] will returns 3). Since dg is an array, array name points to the first element of the array. So after you do the subtract you get the index of the first element in the range from dg[0] to dg[b] which is not less then make_pair(a[i],10000000).
•  » » 8 months ago, # ^ |   0 Pointer is a kind of iterator
•  » » 8 months ago, # ^ |   0 make_pair(a[i],10000000)--->What kind of argument is it???Why I have to write it in the third slot of the funtion???
•  » » » 8 months ago, # ^ |   0 It is the "value you gived". std::make_pair() will return a pair which contains two parameters. If a[i] is an int value then you will get a std::pair object. You find the first element that is not less than this pair.
 » 8 months ago, # |   0 What if you learn your programming language a bit before solving problems?
•  » » 8 months ago, # ^ |   0 More like "learn to look up how unfamiliar features work" instead of spamming questions.
 » 8 months ago, # |   0 Maybe google can help?
•  » » 4 weeks ago, # ^ |   0 yeap.