khisong   1년 전

HLD + lazy로 풀이를 하였는데, pypy3로 했을때 계속해서 메모리 초과가 나길래 python으로 구동을 해보니 시간 초과가 났습니다... pypy3에서 사용되는 메모리량을 최대한 줄여보고자 tree 변수를 빼버렸는데요, pypy3는 동일하게 메모리 초과가 나는데 python으로 통과가 됐습니다. 도대체 무슨차이일까요..?

트리 포함 코드입니다.


zenith82114   1년 전

PyPy는 CPython보다 기본으로 깔고 들어가는 메모리가 훨씬 큰 경향이 있습니다. 그보다 더 중요하게, HLD와 lazy propagation은 이 문제에서는 오버킬입니다.

khisong   1년 전

그러면 HLD만 사용해도 되는거였나요,,??

+ 또 tree에 구간합 저장 안하고 lazy로 update 횟수만 세는 경우가 시간 복잡도 차이를 어떤 식으로 가지는지도 궁금합니다..ㅠ 그냥 근소한 차이로 통과한거일까요?

zenith82114   1년 전

HLD, lazy 둘 다 필요 없습니다. Euler tour technique에 대해 조사해보세요. 추가 질문은 어떻게 푸신 건지 이해가 어려워서 답변이 어렵네요.

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