No.255 Splarrraaay スプラーレェーーイ

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 13
作問者 : LayCurseLayCurse

1 ProblemId : 637 / 出題時の順位表

問題文

Splarrraaay スプラーレェーーイSplarraay スプラレェーイの続編であり、配列を塗りつぶすだけの簡単なゲームです。
プレイヤーはチームAとチームBとチームCとチームDとチームEに分かれ、それぞれのチームを表す色で $1$ つの配列を塗りつぶし合います。
最終的なスコアはそのチームの色で塗りつぶされた要素の数と、後述するボーナスポイントの和で決まり、スコアが高いチームがゲームの勝者となります。

ルール

  1. 長さ $N$ の、何色にも塗られていない配列が与えられる。つまり、全ての要素に対して、それぞれの色の厚みは $0$ である。
  2. $5$ つのチームは配列のある区間 $[l,r]$ をそのチームの色で塗りつぶしていく。
    その際、
    • 何色にも塗られていなかった場合は、それのチームの色で塗られ、そのチームの色の厚みが $1$ となり、
    • 既にそのチームの色で塗られていた要素に関しては、その色の厚みが $1$ だけ増え、
    • 別のチームの色で塗られていた場合は、後から塗られた色で上書きされ、別のチームの色の厚みを $0$ とした後、自分のチームの色の厚みが $1$ となる。
  3. 不定期にボーナスチャンスが与えられる。
    ボーナスチャンスでは区間 $[l,r]$ が与えられ、その時点での区間 $[l,r]$ でのチームXの色の厚みの和を $X_{lr}$($X=A,B,C,D,E$)とすると、この値が最も大きい方のチームに $\max(A_{lr},B_{lr},C_{lr},D_{lr},E_{lr})$ のボーナスポイントが与えられる。
    値が最も大きい物が複数ある場合、どのチームにもボーナスポイントは与えられない。
  4. 時間制限が訪れゲームが終了したとき、配列の全区間 $[0,N−1]$ での、そのチームの色の厚みの和と、それまでに得たボーナスポイントの和がそのチームのスコアとなる。

既にゲームは終了し、後はスコアを計算するだけです。各チームの行動の履歴とボーナスチャンスの詳細が時系列順に与えられるので、最終スコアを算出してください。

入力

$N$
$Q$
$x_1$ $l_1$ $r_1$
$x_2$ $l_2$ $r_2$
$\vdots$
$x_Q$ $l_Q$ $r_Q$

$N$ 塗りつぶし合う配列の長さ
$Q$ 各チームの行動の回数とボーナスチャンスの回数の和。以下 $Q$ 行に渡って行動/ボーナスチャンスの詳細が時系列順に与えられる
$x_k=0$ のとき、区間 $[l_k,r_k]$ のボーナスチャンス
$x_k=1$ のとき、チームAによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=2$ のとき、チームBによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=3$ のとき、チームCによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=4$ のとき、チームDによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=5$ のとき、チームEによる区間 $[l_k,r_k]$ への塗りつぶし行動

また入力は全て整数で与えられ、以下の制約を満たす
$1 \leq N \leq 10^{13}$
$0 \leq Q \leq 150000 = 1.5 \times 10^5$
$0 \leq x_k \leq 5$
$0 \leq l_k \leq r_k < N$

出力

チームAのスコアとチームBのスコアとチームCとチームDとチームEのスコアをそれぞれ ${\rm mod}\ 10^{18}+9$ で空白区切りで出力してください。

サンプル

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

No.230 Splarraay スプラレェーイを参照せよ。

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

No.230 Splarraay スプラレェーイを参照せよ。

サンプル3
入力
6
6
1 1 2
2 4 5
0 2 4
2 0 3
1 1 5
0 0 5
出力
10 1 0 0 0

No.230 Splarraay スプラレェーイを参照せよ。

提出ページヘ