Edited by author 06.02.2016 13:30

Edited by author 06.02.2016 13:38

My result is 0.1 sec, 700 Kb memory usage.

I used VS 2013 (probably its IO works quicker then gcc), C-style (printf/scanf) IO, sorted vector of pairs (count_of_passengers, city_number).

Have a similar solution for Java: HashMap<Integer, TreeSet<Integer>> and floor/ceiling functions. I've got execution time: 0.998 it's kinda funny ))

Edited by author 28.03.2019 12:57

I used the same approach - works much faster 0.218
make sure you are not making unintended copies of the set and use a reference -

std::set<int>& current_set = m[x];
instead of
std::set<int> current_set = m[x];