hwy16016   3년 전

세그먼트 트리로 어찌어찌 풀었는데

더 쉽게 풀 방법은 없는건가요???

djm03178   3년 전

세그먼트 트리 등의 자료구조를 쓰는 것이 정해인 것으로 생각되나, 안타깝게도 단순히 시뮬레이션을 하는 O(nk) 풀이가 통과된다고 합니다. 대단히 유감스러운 부분입니다.

jh05013   3년 전

어제 시간 제한이 바뀌어서 더 이상 O(nk)로 풀 수 없는 문제가 되었습니다.

vector나 Python list를 써도 시간 복잡도는 여전히 O(nk)입니다. 중간에 있는 원소를 삭제하면 그 이후에 있는 모든 원소를 하나하나 앞으로 옮겨야 되기 때문입니다. 따라서 이제는 시간 초과가 날 것입니다.

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