### Zzyzx's blog

By Zzyzx, 6 years ago, ,

Spoiler Alert: This is regarding problem D of the latest Codeforces round (242).

I have two solutions, Let's call them sol-1 and sol-2

In sol-1 I use a struct node

struct node {
int tot, col;
bool operator <(const node &rhs) const {
}
};


In sol-2 I use std::pair <int, int> with the necessary changes to the remaining part of the code.

In sol-1 I get TLE on test case 17.

But In sol-2 I get WA on test case 3.

UPD: Found my mistake. Thank you so much igorjan94 and andreyv

• -2

 » 6 years ago, # |   0 For your struct operator < returns only lhs.tot < rhs.totBut for std::pair the corresponding operator will return lhs.first != rhs.first ? lhs.first < rhs.first : lhs.second < rhs.second
•  » » 6 years ago, # ^ |   0 But that shouldn't give wrong answer.
•  » » » 6 years ago, # ^ |   0 You insert values into a set. With your struct, the set will store at most one element for each tot, ignoring the second value — because from your operator < it follows that all such elements are equal. With pair, the set will store one element per each first/second combination.
•  » » » » 6 years ago, # ^ |   0 I made the change. Still wrong.
•  » » » » » 6 years ago, # ^ |   +8 You can insert debugging output and see that your function isn't even called. If you still want to use pair, you have to define a comparator functor and pass it to std::set and std::upper_bound.
•  » » » » » » 6 years ago, # ^ |   +8 Ok, andreyv . Thanks for your input. I definitely need to brush up my STL knowledge again. :/
•  » » » » » 6 years ago, # ^ |   0 now with std::pair 6474287 TL, not WAyou have written comparator, but didn't use it :)
 » 6 years ago, # | ← Rev. 2 →   +8 because std::pair operator< is template bool operator< (const pair& lhs, const pair& rhs) { return lhs.first
•  » » 6 years ago, # ^ |   0 Thank you SO MUCH igorjan94 . It's so careless of me to use the other version of lower_bound.
•  » » 6 years ago, # ^ |   0 But when you iterate from ::set.begin() to ::set.end() , the elements are in a sorted fashion. So shouldn't the other version of lower_bound also work?
•  » » » 6 years ago, # ^ |   0 yes. if we iterate for (auto it = set.begin(); it != set.end(); ++it), the elements are in a sorted fashion. But std::lower_bound can't get random element. Of course it works, but much slower.
•  » » » 6 years ago, # ^ |   0 std::lower_bound will use something like std::distance and std::advance to operate on the iterator range. But these functions are linear in time if they operate on forward iterators instead of random iterators.