malkoring   5년 전

이 문제가 병렬 이분탐색을 이용해서 푼다는 문제라는 걸 알게 되어서, 병렬 이분탐색을 공부하고 이 문제를 다시 풀게 되었는데

이 문제를 면밀히 분석해본 결과 

  1. DFS 방문순서를 배열로 저장하고, 
  2. 각 쿼리마다 입력되는 점수를 쿼리에서 입력받은 루트노드가 (자기자신을 포함하여) 영향을 미치는 모든 노드에 lazy propagation 을 수행하며,
  3. 계산되는 시간은 시간 순서대로 정렬하고, 
  4. 유성 문제와 같이 풀이

하면 된다는 것은 알았습니다.

그래서, 이것도 역시 웰노운의 교묘한 혼종이겠구나 하고 제가 생각해낼 수 있는 방법을 다 동원해서 풀었는데, 8% 에서 에러가 나네요... 혹시 이 문제를 푸는데 필요한, 제가 알지 못하는 다른 트릭이나 저 코드에서 제가 간과했던 부분이나, 반례 테스트케이스 있을까요?

exqt   5년 전

138줄에 >= 가 아닌 >가 되어야 합니다.

malkoring   5년 전

우와..... 부호 하나 차이로 맞았네요 ㅋㅋㅋ 정말 감사합니다 ㅜㅜ

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