daniel00   6년 전

모든 분들 수고가 많으십니다.

1572번 문제를 몇일째 시도하다가 계속되는 시간초과에 조언을 청해봅니다.

펜윅트리로 구현했고, 여러 정답자 분들의 코드를 참고해서 작성했습니다.

오프라인에서, 10만개짜리 큰 테스트케이스를 만들어 테스트해보았는데 0.2초내로 동작하는데 온라인 제출시 시간초과가 되네요.

도움 부탁드리겠습니다. 감사합니다.

daniel00   6년 전

자답입니다.

입력되는 숫자범위가 0~65536 이므로, 펜윈트리에 빈도수 저장시 인덱스1번 부터 사용하기 위해서는 

idx++ 을 해주어야 하는데 누락되어 있었네요. 역시나 문제조건부터 정확히 파악하여야 할 것 같습니다.

update() / getSum()에 모두 idx++ 적용하니 정답처리 되었네요.

필요하신분 아래 코드 참고하세요.



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