No.945 YKC饅頭

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 81
作問者 : butsurizukibutsurizuki / テスター : 37zigen37zigen
2 ProblemId : 3650 / 出題時の順位表
問題文最終更新日: 2019-12-08 00:23:13

メモ

これはAdvent Calendar Contest 2019の8日目用の問題である.
本日はJOI2019/2020の二次予選当日である.
選手諸君の健闘を祈る.

問題文

Y理事長は,最近yuki饅頭を皿に並べることに夢中である.
yuki饅頭には,YKCの$3$種類の刻印の入った饅頭が存在する.
Y理事長は,以下のルールのもと,左から順に$1,2,...,N$の番号のついた$N$枚の皿に$M$回の操作を施して饅頭を並べていく.

  • $i(1 \le i \le M)$回目の操作では,2つの整数$L_i$と$R_i$と饅頭の種類$T_i$が与えられる.これは,左から$L_i,L_i+1,...,R_i$番目の皿に$T_i$の刻印の入った饅頭を置くことを表す.
  • 但し,各操作について,ある皿にすでに饅頭が置かれている場合,その皿には饅頭を新たに置くことはしない.
$M$回の操作の結果,最終的にどの刻印の饅頭が全体でいくつ置かれたかを求めよ.

入力

入力は以下の形式で標準入力から与えられる.
$N\ M\\
    L_1\ R_1\ T_1\\
    L_2\ R_2\ T_2\\
    \vdots\\
    L_M\ R_M\ T_M$

  • $1 \le N,M \le 200000 (= 2 \times 10^5)$
  • $1 \le L_i \le R_i \le N(1 \le i \le M)$
  • $T_i(1 \le i \le M)$はYKCのいずれかである.

出力

YKCの刻印の入った饅頭が全体でいくつ皿に置かれたかをこの順に空白区切りで$1$行に出力し,最後に改行せよ.

小課題

この問題にはいくつか小課題が設定されている.完解でなければコンテストでの得点は得られないが,自分の解答のレベルの参考にするとよいだろう.

  1. $N,M \le 1000$である.SmallまたはSampleがテストケース名に含まれるようなケースをすべて通過すればこの小課題は認められる.
  2. 追加の制約はない.すべてのテストケースに通過する必要がある.

サンプル

サンプル1
入力
5 2
1 3 Y
3 5 C
出力
3 0 2

  • $1$回目の操作で,$1,2,3$番目の皿にYの印の入った饅頭が置かれる.
  • $2$回目の操作で,$4,5$番目の皿にCの印の入った饅頭が置かれる.$3$番目の皿については,すでにYの印の入った饅頭が置かれており,新たに饅頭が置かれることはない.
  • よってYの印の入った饅頭は$3$個,Kの印の入った饅頭は$0$個,Cの印の入った饅頭は$2$個置かれたことになる.

サンプル2
入力
8 7
3 6 Y
1 5 C
1 1 Y
5 7 C
3 4 Y
5 6 K
4 7 Y
出力
4 0 3

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