기존 풀이 방법은 아니긴 한데 Merge-sort tree 를 사용해서 nlog^2n에 메모리 nlogn으로 돌아가는 풀이 방법이 있습니다. 시간상수 차이로 시간초과가 뜨는 것 같은데, 시간제한을 대략 2~3초 정도로 연장시켜 주시면 좋을 것 같습니다. 문제 특성상 n^2풀이가 돌아갈 가능성은 없어 보이고, 기존 제출자(puppy) 풀이 중에서도 812ms에 가까운 시간 동안 돌아가는 것이 있어 시간 초과가 나기 쉬워 보입니다. 시간 제한을 2~3초로 늘려서 풀어주시면 감사하겠습니다.
johnny8337 3년 전 1
기존 풀이 방법은 아니긴 한데 Merge-sort tree 를 사용해서 nlog^2n에 메모리 nlogn으로 돌아가는 풀이 방법이 있습니다. 시간상수 차이로 시간초과가 뜨는 것 같은데, 시간제한을 대략 2~3초 정도로 연장시켜 주시면 좋을 것 같습니다. 문제 특성상 n^2풀이가 돌아갈 가능성은 없어 보이고, 기존 제출자(puppy) 풀이 중에서도 812ms에 가까운 시간 동안 돌아가는 것이 있어 시간 초과가 나기 쉬워 보입니다. 시간 제한을 2~3초로 늘려서 풀어주시면 감사하겠습니다.