Green55   4달 전

풀이의 흐름은 다음과 같습니다

  1. 초기 퀘스트의 목록과 쿼리의 목록을 미리 받아놓습니다.
  2. 1에서 등장한 모든 퀘스트들을 좌표 압축 시킵니다.
  3. 현재 깬 퀘스트 목록을 펜윅트리를 이용해 관리하고, 쿼리는 이분 탐색을 이용해 적절히 구해줍니다.

O(Mlog(N+M))이어서 맞을거라고 생각했는데 시간초과가 나네요. 어디를 고쳐야 할까요?

zlzmsrhak   4달 전

  1. 입력 양이 많다보니 cin 대신 scanf를 써야 합니다.
  2. 좌표압축을 할 때는 map이 매우 느리기 때문에, map 대신 vector나 배열만을 사용하여 전처리하는 것이 더 빠릅니다.

jh05013   4달 전

sync_with_stdio와 cin.tie를 끈 cin, cout이 scanf, printf보다 빠릅니다.

https://www.acmicpc.net/blog/v...

https://www.acmicpc.net/blog/v...

zlzmsrhak   4달 전

로컬에서 8배 넘게 차이나서 BOJ에서도 차이가 많이 날 줄 알았는데 비슷하다니 신기하네요..


좌표압축을 map에서 vector + lower_bound로 바꾸는 것만으로 3초 안에 나오는것을 확인했습니다.

이런 문제처럼 시간복잡도는 O((M+N)log(N+M))이지만 코드 자체가 느리기 때문에 시간초과가 날 수 있습니다.

특히, map이나 set같은 stl은 매우 느리기 때문에 조심해서 사용할 필요가 있습니다.

Green55   4달 전

덕분에 좋은걸 배워갑니다 감사합니다!!

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