list에 삽입할 값을 lower_bound로 찾아서 insert를 해주는 식으로 처음에 짜봤는데 시간 초과가 나더라구요.

결국에는 multiset으로 풀었는데 어디서 차이가 나는건가요??

삽입할 값의 위치를 탐색하는데 O(logN), 찾은 위치에 insert 하는거니까 O(1)이라 생각했는데 아닌가요??