BOJ 31480 양갈래 바이러스

문제 링크:

문제 내용

정점의 개수가 $N$인 포화 이진 트리가 있습니다. 정점 $i > 1$은 정점 $\lfloor \frac{i}{2} \rfloor$를 부모로 갖습니다.

각 정점의 현재 값은 모두 0입니다. 다음의 쿼리가 $Q$개 주어질 때, 모든 쿼리가 종료된 후의 각 정점의 값을 출력하세요.

• v p d: 정점 $v$에서 거리 $d$ 이하인 모든 정점에 $p$를 더합니다. 두 정점 $a$와 $b$의 거리는 정점 $a$에서 정점 $b$로 가기 위해 거쳐야 하는 간선의 최소 개수로 정의합니다.

입력

첫 줄에 $N$과 $Q$가 주어집니다. ($1 \le N < 2^{18}$, $1 \le Q \le 200\;000$)

다음 $Q$개 줄에는 각 쿼리의 정보가 주어집니다. ($1 \le v \le N$, $1 \le p \le 1000$, $0 \le d \le 2(\log_2 (N+1) - 1)$)

출력

1번부터 $N$번 정점까지 순서대로 각 정점의 값을 한 줄에 공백으로 구분하여 출력합니다.

문제 풀이