골드 IV알파카 왕국에는 길이 \(N\)의 거대한 도로가 있다.
알파카 왕국의 왕 경현이는 이 도로에 조명을 설치하려 한다. 위치 \(X\)에 밝기 \(L\)의 조명을 설치하면, 그곳에서 거리 \(d\)만큼 떨어진 지점의 밝기에 \(\max(0,\ L-d)\)만큼이 더해진다.
예를 들어 \(N = 5\)이고 도로 각 지점의 밝기가 \(0\ 1\ 1\ 0\ 0\)일 때, 위치 \(3\)에 밝기 \(2\)의 조명을 설치하면 각 지점의 밝기는 \(0\ 2\ 3\ 1\ 0\)이 된다.
현재 모든 지점의 밝기는 \(0\)이다. 경현이는 총 \(M\)개의 조명을 설치할 계획이며, \(i\)번째 조명의 위치는 \(X_i\), 밝기는 \(L_i\)이다.
\(M\)개의 조명을 모두 설치했을 때 각 지점의 밝기를 계산하는 프로그램을 작성하시오.
-
\(1 \le N, M \le 1{,}000{,}000\)
-
\(1 \le X_i, L_i \le N\)
-
모든 입력값은 정수이다.
첫째 줄에 정수 \(N\)과 \(M\)이 주어진다.
둘째 줄부터 \(M\)개의 줄에 두 정수 \(X_i\), \(L_i\)가 주어진다.
\(1\)번부터 \(N\)번까지 각 지점의 최종 밝기를 공백으로 구분하여 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 5점 | \(M = 1\) |
Subtask 2 | 5점 | \(L_i = 1\) |
Subtask 3 | 15점 | 모든 조명의 위치가 같다. |
Subtask 4 | 30점 | \(N, M ≤ 1,000\) |
Subtask 5 | 45점 | 추가 제약 조건 없음. |
5 3
2 1
3 2
1 33 4 3 1 0초기 상태에는 \(0\ 0\ 0\ 0\ 0\)이다.
위치 2에 밝기 1의 조명을 설치하면 \(0\ 1\ 0\ 0\ 0\)이 되고,
위치 3에 밝기 2의 조명을 설치하면 \(0\ 2\ 2\ 1\ 0\),
위치 1에 밝기 3의 조명을 설치하면 \(3\ 4\ 3\ 1\ 0\)이 된다.
최종적인 답은 \(3\ 4\ 3\ 1\ 0\)이다.
pythonprominhyeong 작성
출처 @pythonprominhyeong
