13548번 - 수열과 쿼리 6
계속 봐도 왜 시간초과가 뜨는 지 모르겠에서, 혹시 제가 오해하는 부분이 있나 해서 질문합니다.
벡터 대신 세트에 등장 횟수랑 숫자를 기록하고, 또 다른 배열에서 개수를 관리하는 방식을 채택했습니다.
그러면 매 add, remove마다 log(100001)=16.~ 정도 소모되는데, 사실상 log(N)이라 쳐도 됩니다.
곧 시간복잡도가 O((N+Q)log(N)sqrt(N))인데 왜 시간초과가 나나요?
라고 질문을 하려 했는데 보니까 숫자가 좀 크네요 ㅎㅎ 혹시 저처럼 왜 안되나 싶었다면 참고하세요
댓글을 작성하려면 로그인해야 합니다.
n4435898 1년 전
계속 봐도 왜 시간초과가 뜨는 지 모르겠에서, 혹시 제가 오해하는 부분이 있나 해서 질문합니다.
벡터 대신 세트에 등장 횟수랑 숫자를 기록하고, 또 다른 배열에서 개수를 관리하는 방식을 채택했습니다.
그러면 매 add, remove마다 log(100001)=16.~ 정도 소모되는데, 사실상 log(N)이라 쳐도 됩니다.
곧 시간복잡도가 O((N+Q)log(N)sqrt(N))인데 왜 시간초과가 나나요?
라고 질문을 하려 했는데 보니까 숫자가 좀 크네요 ㅎㅎ 혹시 저처럼 왜 안되나 싶었다면 참고하세요