To quickly find the first word that matches the prefix, we can use binary search on the sorted dictionary. This reduces the running time to O(N * L * log(W)). The full solution below uses C++'s convenient "lower_bound" function
не подскажете ли почему у большинства участников олимпиад, пишущих на c++, не принято использовать map. это методика обучения такая(запрет на использование) или никто не знает что это такое? задачу "Сортировка подсчётом" большинство решило без map. да и вообще, складывается впечатление, что большинство пишет на с++ больше формально(используется в основном сишный функционал)