mrcamel   1년 전

삽입할 숫자를 t라고 하면

[1,t)에서 t와 가장 가까이 있는 수

(t,n]에서 t와 가장 가까이 있는 수

둘 중 하나의 자식이라서 이진탐색과 BIT를 써서 O( n(logn)^2 ) 안에 해결 가능 할 줄 알았는데 시간초과가 발생하네요.

300000 1 2 3 4 .. 300000 의 경우 BOJ코딩에서 300ms 정도로 통과하는데 이보다 더 느린 경우가 있을까요?


8 3 5 1 6 8 7 2 4의 경우

lv[i]12345678
0
01
101
1012
10123
101243
1201243
12021243



pichulia   1년 전

https://www.acmicpc.net/coding/view/4418


O(n*(logn)^2) 정도면 n이 300,000 일 때 잘만하면 TLE가 나올 수 있는 크기입니다....ㅠㅠ

위의 코드는 인덱스트리가 밸런스되게 (중간에 노이즈좀 넣어주고...) 데이터를 넣은 경우입니다.

데이터 만드느라 시간이 소비되서 1초가 된거같기도 한데...아무튼 이런 경우에 시간이 꽤 걸리네요


mrcamel   1년 전

감사합니다!

공식 홈페이지에는 map으로 O nlogn 으로 풀던데 좀 생각해봐야겠네요 ㅠㅠ

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