veydpz   4년 전

세그먼트 트리를 사용해서 시간 복잡도를 O(n + m lg(n)) 을 만들었는데, TLE가 뜹니다.

이전에 있었던 이 문제에 대한 질문의 댓글대로, 세그먼트 트리가 아니라 1000개씩 묶어서 최솟값 구해놓는 방법 또한 고려해 보았습니다만, O(n + m*n/1000)이므로 세그먼트 트리로 풀었을 때와 비슷한 속도를 보일 것 같습니다.

위의 두 방법 외에 더 좋은 방법이 있나요? ㅜㅜ 혹시 몰라서 세그먼트 트리로 푼 코드를 첨부합니다.

veydpz   4년 전

자문자답합니다. 10번째 줄에서 x!=y가 아니라 x<y 로 고쳐야 되네요. 아니면 무한루프 때문에 TLE...

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