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

Link to problem statement: http://mirror.codeforces.com/contest/424/problem/D

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

Link to sol-1: http://mirror.codeforces.com/contest/424/submission/6472455

Link to sol-2: http://mirror.codeforces.com/contest/424/submission/6472637

In sol-1 I use a struct node

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

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.

How is that possible?! Can someone please help me out?

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

For your struct

`operator <`

returns onlyBut for

`std::pair<int, int>`

the corresponding operator will returnBut that shouldn't give wrong answer.

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<int, int>`

, the set will store one element per each`first`

/`second`

combination.I made the change. Still wrong.

Link: http://mirror.codeforces.com/contest/424/submission/6474158

You can insert debugging output and see that your function isn't even called. If you still want to use

`pair<int, int>`

, you have to define a comparator functor and pass it to`std::set`

and`std::upper_bound`

.Ok, andreyv . Thanks for your input. I definitely need to brush up my STL knowledge again. :/

now with std::pair 6474287 TL, not WA

you have written comparator, but didn't use it :)

because std::pair operator< is

your solution, but accepted 6474171

difference is in lower/upper_bound. You used this, and set doesn't have random access iterator so works linear time, but I changed it to this and it works in logarithmic time

Thank you SO MUCH Igorjan94 . It's so careless of me to use the other version of lower_bound.

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?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.`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.