Rose   2년 전

lazy propagation으로 주고나서 나중에 lazy값들 싹다 모아서 한번 갱신시키고 수식하나로 기차표*n이 싼지 카드 초기구입+ 카드 회마다 비용*n중에서 작은걸로 골라서 넣었는데 3%쯤에서 틀렸다뜨네요

한번만 읽어봐주세요ㅠㅠㅠㅠ

chogahui05   2년 전

제가 lazy를 안 배워서 그런데요..

구간 합을 구하는 연산에서도 propergation이 일어나지 않나요? 구간 합을 구할 때 어짜피 lazy 값이 반영되는 걸로 알고 있는데.

main에서 굳이 처리할 필요는 없다고 생각합니다. sum 함수를 구현하면 될 거 같고요.

사실 접근법이 틀리지는 않았습니다. 그렇다는 이야기는

오버플로우 가능성이라던지.. 혹은 lazy를 잘못 구현했는지에 대해서 체크를 하셔야 하는데요. 제가 lazy는 잘 모르니.. 답변을 해 드릴 순 없고.

lazy 말고도 더 쉽게 푸는 방법이 있습니다. sorting을 하고 pq를 쓰는 건데요.

재작년 acmicpc 예선에 나온 철로 문제를 그런식으로 풀 수 있고요. 이 문제하고 거의 동치임을 알 수 있어요. 단지 이 문젠

추가로 구현해야 하는 게 조금 더 있을 뿐이지요.

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