onlyhim   2년 전

N이 5e6이고 출력이 N번 이루어져야 하므로

세그먼트 트리를 이용하면

출력 N번 * 최소값 쿼리 logN이므로 충분하다고 생각했는데 시간초과가 나오네요

제가 잘못이해하고 있는 부분 설명 부탁드리겠습니다

thexl   2년 전

마지막에 O(N) 풀이법이 있는 것 같네요.

https://pgr21.com/pb/pb.php?id...

onlyhim   2년 전

@thexl

감사합니다.

deque를 이용한 O(N) 풀이법이 있다는 것을 알고는 있는데

해당 문제는 NlgN을 이용한 세그먼트 트리가 불가능한건지,

혹은 제가 문제를 아예 잘못이해하고 있는지 궁금합니다.

djm03178   2년 전

5백만 개의 입출력은 그 자체로 시간이 많이 걸립니다. 수 정렬하기 3 문제랑도 비교해볼 수 있는데, 최대 5자리의 수 천만개를 입력받고 O (N) 시간에 정렬하여 다시 출력하는데 2초가 넘게 소요됩니다. 여기서 시간을 대부분 소모하는 건 입출력입니다. 그렇기 때문에 이 문제에서도 3초라는 시간이 N lg N을 통과시켜주기 위해 있는 게 아닙니다. 설령 각 연산이 아주 가볍더라도 기본적으로 1억 정도가 되기 때문에 어렵습니다.

onlyhim   2년 전

@djm03178

이해됬습니다. 감사합니다 좋은하루되세요~

gjs001   2년 전

세그먼트 트리로도 풀립니다. 다만 입출력에서 scanf를 쓰거나 ios::sync_with_stdin(false); 구문을 쓴 상태에서 cin을 사용해야 할 듯요.

세그먼트 트리 문제로 분류되어 있는데 안풀리면 이상하긴하죠!

onlyhim   2년 전

@gjs001


입출력 모두 printf, scanf사용하는데 시간초과가 뜹니다ㅜ

세그먼트트리의 구현에서 잘못된것 같습니다..

djm03178   2년 전

음... 상수배에서 갈릴 수 있는 정도라면 시간을 조금 더 넉넉하게 두었어야 할 것 같기도 하네요.

gjs001   2년 전

@onlyhim

세그먼트 트리 초기화 할 때 혹시 무한대 값을 모든 트리 노드에다가 다 넣어주시나요? 아마 이러면 시간초과 날 듯 합니다.

저는 마지막 리프 노드 +1에다가만 무한대 값 넣어줬어요. 마지막 리프노드가 오른쪽에서 끝나면 어차피 안쓰일거고 왼쪽에서 쓰일 경우만 잘 거르게요.

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