D - Highlighting with a Fluorescent Pen Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、試験勉強のために教科書の重要な部分に蛍光ペンでマーキングをしています。

教科書のある行に注目します。この行には N 文字が横一列に並んでおり、左から順に位置 1, 2, \ldots, N と番号が付いています。

高橋君が使っている蛍光ペンは、一度ペンを引くと連続する W 文字分をマーキングします。高橋君はこの蛍光ペンを合計 K 回使用しました。i 回目 (1 \leq i \leq K) のマーキングでは、開始位置 L_i を選び、位置 L_i から位置 L_i + W - 1 までの連続する W 文字をマーキングしました。ただし、マーキング範囲が行からはみ出すことはありません（すなわち 1 \leq L_i \leq N - W + 1 が成り立ちます）。

異なる回のマーキングで同じ開始位置が選ばれることもあります。また、開始位置が異なっていてもマーキング範囲が重なることがあります。各位置の文字がマーキングされた回数は、その位置を含むマーキング操作の回数の合計です。

すべてのマーキング作業が終わった後、各位置の文字が合計で何回マーキングされたかを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq N
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq L_i \leq N - W + 1 (1 \leq i \leq K)
  • 入力はすべて整数

入力

N W K
L_1
L_2
\vdots
L_K
  • 1 行目には、文字の総数 N 、蛍光ペンで一度にマーキングされる文字数 W 、マーキングの回数 K がスペース区切りで与えられる。
  • 続く K 行のうち i 行目 (1 \leq i \leq K) には、 i 回目のマーキングの開始位置 L_i が与えられる。

出力

N 個の整数をスペース区切りで 1 行に出力せよ。 j 番目 (1 \leq j \leq N) の整数は、位置 j の文字がマーキングされた回数を表す。

入力例 1

10 3 2
2
5

出力例 1

0 1 1 1 1 1 1 0 0 0

入力例 2

8 4 3
1
3
2

出力例 2

1 2 3 3 2 1 0 0

入力例 3

15 5 6
1
3
7
11
2
7

出力例 3

1 2 3 3 3 2 3 2 2 2 3 1 1 1 1

Score : 366 pts

Problem Statement

Takahashi is highlighting important parts of his textbook with a fluorescent marker while studying for exams.

Consider a particular line in the textbook. This line contains N characters arranged in a horizontal row, numbered from left to right as positions 1, 2, \ldots, N.

The fluorescent marker Takahashi uses marks W consecutive characters each time it is used. Takahashi used this fluorescent marker a total of K times. In the i-th marking (1 \leq i \leq K), he chose a starting position L_i and marked the W consecutive characters from position L_i to position L_i + W - 1. The marking range never extends beyond the line (that is, 1 \leq L_i \leq N - W + 1 holds).

The same starting position may be chosen in different markings. Also, even if starting positions differ, their marking ranges may overlap. The number of times a character at each position is marked is the total number of marking operations that include that position.

After all marking operations are completed, determine how many times the character at each position was marked in total.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq N
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq L_i \leq N - W + 1 (1 \leq i \leq K)
  • All inputs are integers

Input

N W K
L_1
L_2
\vdots
L_K
  • The first line contains the total number of characters N, the number of characters marked at once by the fluorescent marker W, and the number of markings K, separated by spaces.
  • The i-th (1 \leq i \leq K) of the following K lines contains the starting position L_i of the i-th marking.

Output

Output N integers separated by spaces on a single line. The j-th (1 \leq j \leq N) integer represents the number of times the character at position j was marked.

Sample Input 1

10 3 2
2
5

Sample Output 1

0 1 1 1 1 1 1 0 0 0

Sample Input 2

8 4 3
1
3
2

Sample Output 2

1 2 3 3 2 1 0 0

Sample Input 3

15 5 6
1
3
7
11
2
7

Sample Output 3

1 2 3 3 3 2 3 2 2 2 3 1 1 1 1