jh05013   2달 전

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

djm03178   2달 전

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   2달 전

재귀 세그트리만 막힌 것이었군요. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.