C++에서 O(NlogN)이 막힌 건 재귀 세그트리 정도이고, 삭제 가능 힙을 구현하면 O(NlogN)으로도 제법 여유있게 통과가 됩니다. https://www.acmicpc.net/source...
그리고 fast I/O를 한 결과를 보면 NlogN이 차지하는 비중이 그렇게 높지도 않습니다. https://www.acmicpc.net/source... 는 덱 사용으로 O(N)에 구현한 것이고, https://www.acmicpc.net/source/12892875 는 우선순위 큐로 O(NlogN)을 한 것인데 둘의 차이가 많이 나지도 않을 뿐더러 O(NlogN)이 500ms 안에 들어옵니다.
해당 코드 역시 힙을 사용한 pq인 것으로 보이는데 단지 O(NlogN)이라는 이유만으로 막혀야 할지는 조금 의문입니다.
jh05013 4년 전
C++과 자바 시간 제한이 O(N)만 통과되도록 설정되었는데, 파이썬 제한이 기본 설정으로 되어서 O(NlogN) 풀이가 통과합니다. (채점 번호 9166196)
저의 수행 시간은 다음과 같습니다: https://www.acmicpc.net/status?problem_id=11003&user_id=jh05013&language_id=-1&result_id=-1&from_mine=1