No.1021 Children in Classrooms

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 193
作問者 : chocoruskchocorusk / テスター : ningenMeningenMe
20 ProblemId : 4030 / 出題時の順位表
問題文最終更新日: 2020-04-08 14:28:44

問題文

yuki小学校には $1, 2, \ldots , N$ の番号がついた $N$ 個の教室がこの順に左から横一列に並んでいます。はじめ、教室 $i$ ($1\leq i \leq N$) には $a_i$ 人の児童がいます。yuki先生は $M$ 回の号令をかけます。号令には次のようなタイプLとタイプRの $2$ 種類があります。

  • タイプLの号令を行うと、教室 $1$ 以外にいる児童全員が同時にひとつ左の教室に移動する。
  • タイプRの号令を行うと、教室 $N$ 以外にいる児童全員が同時にひとつ右の教室に移動する。
yuki先生が行う $M$ 回の号令の情報が文字列 $S$ で与えられます。$S_i$ が L のとき $i$ 回目の号令はタイプLであり、$S_i$ が R のとき $i$ 回目の号令はタイプRです。$M$ 回の号令後に各教室にいる児童の数を求めてください。

入力

$N\ M$
$a_1\ a_2\ \ldots\ a_N$
$S$

  • $2\leq N\leq 2\times 10^5$
  • $1\leq M\leq 2\times 10^5$
  • $0\leq a_i\leq 10^4$
  • $N$, $M$, $a_i$ は整数である。
  • $S$ は長さ $M$ の文字列である。
  • $S$ の各文字は L または R である。

出力

$N$ 個の整数を空白区切りで出力せよ。左から $i$ 個目 ($1\leq i\leq N$) の整数は、$M$ 回の号令後に教室 $i$ にいる児童の数とすること。

サンプル

サンプル1
入力
4 3
3 1 4 1
LRR
出力
0 0 4 5

  • $1$ 回目の号令後に教室 $1, 2, 3, 4$ にいる児童の数は順に $4, 4, 1, 0$ です。
  • $2$ 回目の号令後に教室 $1, 2, 3, 4$ にいる児童の数は順に $0, 4, 4, 1$ です。
  • $3$ 回目の号令後に教室 $1, 2, 3, 4$ にいる児童の数は順に $0, 0, 4, 5$ です。

サンプル2
入力
2 7
1 8
LLLLLLL
出力
9 0

$2$ 回目以降の号令では誰も移動しません。

サンプル3
入力
5 6
314 0 1 5 9
RLRLLR
出力
0 314 1 14 0

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