F - Usual Color Ball Problems Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

正整数 N, M, K と、長さ N の正整数列 (C_1, C_2, \ldots, C_N) が与えられるので、 r = 0, 1, 2, \ldots, N-1 の場合それぞれについて、下記の問題の答えを出力してください。

色がついた N 個のボールからなる列があり、i = 1, 2, \ldots, N について、列の先頭から i 番目にあるボールの色は C_i です。 また、1 から M の番号がつけられた M 個の空の箱があります。

下記の手順を行った後に箱に入っているボールの総数を求めてください。

  • まず、下記の操作を r 回行う。

    • 列の先頭のボール 1 個を列の最後尾に移動する。

  • その後、列にボールが 1 個以上残っている限り、下記の操作を繰り返す。

    • 列の先頭のボールと同じ色のボールが既に 1 個以上 K 個未満入っている箱が存在する場合、その箱に列の先頭のボールを入れる。
    • そのような箱が存在しない場合、
      • 空の箱が存在するなら、そのうち番号が最小のものに、列の先頭のボールを入れる。
      • 空の箱が存在しない場合、列の先頭のボールをどの箱にも入れず、食べる。

制約

  • 入力される値はすべて整数
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M, K \leq N
  • 1 \leq C_i \leq N

入力

入力は以下の形式で標準入力から与えられる。

N M K
C_1 C_2 \ldots C_N

出力

r = 0, 1, 2, \ldots, N-1 のそれぞれの場合の問題の答え X_r を下記の通りに N 行にわたって出力せよ。

X_0
X_1
\vdots
X_{N-1}

入力例 1

7 2 2
1 2 3 5 2 5 4

出力例 1

3
3
3
4
4
3
2

例として、r = 1 の場合の手順を説明します。 まず「列の先頭のボール 1 個を列の最後尾に移動する」ことを 1 回行い、ボールの色の列は (2, 3, 5, 2, 5, 4, 1) となります。 その後、ボールを箱に入れていく操作を下記の通りに行います。

  • 1 回目の操作：先頭のボールの色は 2 です。色 2 のボールが 1 個以上 2 個未満入った箱は存在しないため、先頭のボールを空の箱のうち番号が最小の箱 1 に入れます。
  • 2 回目の操作：先頭のボールの色は 3 です。色 3 のボールが 1 個以上 2 個未満入った箱は存在しないため、先頭のボールを空の箱のうち番号が最小の箱 2 に入れます。
  • 3 回目の操作：先頭のボールの色は 5 です。色 5 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
  • 4 回目の操作：先頭のボールの色は 2 です。色 2 のボールが 1 個以上 2 個未満入った箱として箱 1 が存在するため、先頭のボールを箱 1 に入れます。
  • 5 回目の操作：先頭のボールの色は 5 です。色 5 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
  • 6 回目の操作：先頭のボールの色は 4 です。色 4 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。
  • 7 回目の操作：先頭のボールの色は 1 です。色 1 のボールが 1 個以上 2 個未満入った箱も空の箱も存在しないため、先頭のボールを食べます。

最終的に箱に入っているボールの総数は 3 個であるので、r = 1 の問題の答えは 3 です。

入力例 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

出力例 2

14
14
14
14
13
13
13
11
8
9
9
11
13
14
14
14
14
14
14
13

Score: 550 points

Problem Statement

You are given positive integers N, M, K, and a sequence of positive integers of length N, (C_1, C_2, \ldots, C_N). For each r = 0, 1, 2, \ldots, N-1, print the answer to the following problem.

There is a sequence of N colored balls. For i = 1, 2, \ldots, N, the color of the i-th ball from the beginning of the sequence is C_i. Additionally, there are M empty boxes numbered 1 to M.

Determine the total number of balls in the boxes after performing the following steps.

  • First, perform the following operation r times.

    • Move the frontmost ball in the sequence to the end of the sequence.

  • Then, repeat the following operation as long as at least one ball remains in the sequence.

    • If there is a box that already contains at least one but fewer than K balls of the same color as the frontmost ball in the sequence, put the frontmost ball into that box.
    • If there is no such box,
      • If there is an empty box, put the frontmost ball into the one with the smallest box number.
      • If there are no empty boxes, eat the frontmost ball without putting it into any box.

Constraints

  • All input values are integers.
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M, K \leq N
  • 1 \leq C_i \leq N

Input

The input is given from Standard Input in the following format:

N M K
C_1 C_2 \ldots C_N

Output

Print the answer X_r to the problem for each r = 0, 1, 2, \ldots, N-1 over N lines as follows:

X_0
X_1
\vdots
X_{N-1}

Sample Input 1

7 2 2
1 2 3 5 2 5 4

Sample Output 1

3
3
3
4
4
3
2

For example, let us explain the procedure for r = 1. First, perform the operation "Move the frontmost ball in the sequence to the end of the sequence" once, and the sequence of ball colors becomes (2, 3, 5, 2, 5, 4, 1). Then, proceed with the operation of putting balls into boxes as follows:

  • First operation: The color of the frontmost ball is 2. There is no box with at least one but fewer than two balls of color 2, so put the frontmost ball into the empty box with the smallest box number, box 1.
  • Second operation: The color of the frontmost ball is 3. There is no box with at least one but fewer than two balls of color 3, so put the frontmost ball into the empty box with the smallest box number, box 2.
  • Third operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
  • Fourth operation: The color of the frontmost ball is 2. There is a box, box 1, with at least one but fewer than two balls of color 2, so put the frontmost ball into box 1.
  • Fifth operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
  • Sixth operation: The color of the frontmost ball is 4. There is no box with at least one but fewer than two balls of color 4 and no empty boxes, so eat the frontmost ball.
  • Seventh operation: The color of the frontmost ball is 1. There is no box with at least one but fewer than two balls of color 1 and no empty boxes, so eat the frontmost ball.

The final total number of balls in the boxes is 3, so the answer to the problem for r = 1 is 3.

Sample Input 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

Sample Output 2

14
14
14
14
13
13
13
11
8
9
9
11
13
14
14
14
14
14
14
13