타 온라인 저지에선 ac가 뜨는 소스거든요 scanf보다 cin cout쓰는게 빠를꺼 같아서 그걸로도 바꿔보고 배열 두개에다가 다 넣는게 정렬하는데 시간이 더 걸릴까봐 그것도 줄였구요. 배열 크기잡는 변수 크기 올리는데도 시간 걸릴까봐 그것까지 없앴어요. lowerbound하고 upperbound는 O(logn)이니까 더이상 줄일 수가 없는데 왜 자꾸 tle가 뜨는건가요;;

안녕하세요. 요새 눈팅만 대충 하고있는 불쌍한 대학원생 도비 pichulia 입니다. 원래 지금 코드처럼 작성한 N^2log(N^2)은 수행시간이 약 5초정도이며, 이녀석은 TLE를 내고, 좀 더 최적화된 3초짜리 풀이를 유도하는 문제였지만... 5초짜리 풀이가 생각보다 많은거같아서 그냥 시간제한을 5초로 늘렸습니다.

조교님 궁금한데 3초짜리랑 5초짜리랑 뭐가 다른가요? 전 std::sort() 썼더니 3초가 나왔습니다. qsort()같은걸 쓰면 5초가 나오나요? 궁금하네요

제 경우엔 qsort함수를 구현해서 했을떄가 std::sort보다 더 빠른계산이 나왔네요... 그냥 알고리즘 방식의 차이가 아닐련지 흠.

sort는 관계 없습니다;;

binary search를 쓰느냐 안쓰느냐의 차이죠. 쓰면 5초 안쓰면 3초입니다.

흠 전 바이너리서치 안쓰고 3초 나오긴 했는데... 소팅하는데 N^2log(N^2) 걸려서 O(N^2log(N^2)) 라고 생각했는데 아닌가요? 소팅만하고 바이너리서치 안쓸리는없고 5초나오는 알고리즘이 궁금하네요ㅠㅠ