kyo20111   4년 전

세그먼트 트리를 만드는데 드는 시간 : nlogn = 대략 22 * 5000000 = 110000000

쿼리를 보는데 드는 시간 : nlogn

해서 2nlogn으로 2억2천번의 연산을 본다치면 2.4초 안에 들어올 수 있는정도 아닌가요?

코드도 첨부해봅니다.

exqt   4년 전

정해가 deque을 이용한 슬라이딩 윈도우인거 같은데 제한시간에 매우 가깝게 나오네요

재귀 새그 트리로는 힘들어보입니다

kyo20111   4년 전

그렇군요 ㅠㅠ 답변 감사합니다.

dyk777   4년 전

저도 세그트리로 풀었었는데, 시간초과났더군요.

재귀->비재귀로 고치고, 입출력 방식까지 고쳐서 0.1~0.2초차이로 겨우 통과되었네요.

윗분 말씀대로 재귀로는 힘듦~불가능이 아닐까 싶습니다.

djm03178   4년 전

임의의 원소의 삭제가 가능한 힙을 구현하면 똑같이 O(NlogN)이지만 훨씬 빠르기 때문에 빠른 입출력을 쓰지 않아도 통과할 수 있습니다.

kyo20111   4년 전

예전에  2524ms로 AC맞았다가 시간제한을 수정하면서 시간초과난 코드입니다.

여기서 시간을 더 줄이는 방법을 몰라 포기하고 세그먼트 트리로도 짜본 것인데 빠른 입출력을 사용하면 AC맞을수 있을까요?

djm03178   4년 전

입출력이 많은 문제에서는 입출력 시간이 웬만한 NlogN보다 훨씬 큽니다. 빠른 입출력으로 엄청나게 줄일 수 있습니다.

kyo20111   4년 전

빠른 입출력을 사용하는 방법을 몰라서 소개하는 내용이 있는 곳이 있나요?..

kyo20111   4년 전

cin cout으로 고치니깐 맞았습니다! 감사합니다

dohoon   2년 전

저도 궁금했던 부분인데 감사합니다!

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