問題一覧 > 通常問題

No.606 カラフルタイル

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 88
作問者 : FF256grhyFF256grhy / テスター : はむこはむこ
8 ProblemId : 2011 / 出題時の順位表
問題文最終更新日: 2017-11-28 16:48:30

問題文

$N$ 行 $N$ 列に並べた $N^2$ 個のタイルに色を塗っていきます。色は $1$ 番から $K$ 番までの $K$ 色あり、最初は全てのタイルが $1$ 番の色で塗られています。着色作業は計 $Q$ 回行われ、$i$ 回目の作業では、$A_i$ が "R" であれば $B_i$ 行目、"C" であれば $B_i$ 列目のタイルを全て $C_i$ 番の色に塗り替えます。最終的にどの色のタイルが何枚存在することになるかを答えてください。

入力

$N$ $K$ $Q$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_Q$ $B_Q$ $C_Q$

入力は $A_i$ ($1 \leq i \leq Q$) を除き全て整数で、以下の制約を満たします。
$1 \leq N \leq 10^5$
$1 \leq K \leq 10^5$
$1 \leq Q \leq 10^5$
$A_i$ は "R" または "C" である ($1 \leq i \leq Q$)
$1 \leq B_i \leq N$ ($1 \leq i \leq Q$)
$1 \leq C_i \leq K$ ($1 \leq i \leq Q$)

出力

最終的に $i$ 番の色になるタイルの個数を $i$ 行目に出力してください ($1 \leq i \leq K$) 。最終行も含め、各行の終わりでは改行を出力してください。

サンプル

サンプル1
入力
3 4 6
C 1 2
C 2 3
R 2 1
C 3 4
R 3 3
C 2 1
出力
4
1
2
2

以下のように色が塗られます。

サンプル2
入力
1 5 2
R 1 4
R 1 4
出力
0
0
0
1
0

一度も使われない色があることもあります。

サンプル3
入力
100000 2 1
R 12345 2
出力
9999900000
100000

答えとなる値は 32 bit 整数型に収まるとは限らないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。