No.230 Splarraay スプラレェーイ

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

5 ProblemId : 625 / 出題時の順位表

問題文

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

ルール

  1. 長さ$N$の、何色にも塗られていない配列が与えられる
  2. 2つのチームは配列のある区間$[l,r]$をそのチームの色で塗りつぶしていく。塗りつぶそうとした場所に既に色が塗られていた場合、後から塗られた色で上書きされる
  3. 不定期にボーナスチャンスが与えらる。ボーナスチャンスでは区間$[l,r]$が与えられ、その時点でチームAによって塗られている区間$[l,r]$の要素の数を$A_{l,r}$ 、チームBによって塗られている区間$[l,r]$の要素の数を $B_{l,r}$ としたとき、この値が大きい方のチームに $max(A_{l,r}, B_{l,r})$ のボーナスポイントが与えられる。 $A_{l,r}$ と $B_{l,r}$ が等しい場合、どちらにもボーナスポイントは与えられない
  4. 時間制限が訪れゲームが終了したとき、配列の全区間$[0,N-1]$の、そのチームの色で塗られている要素の数と、それまでに得たボーナスポイントの和がそのチームのスコアとなる

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

入力

$N$
$Q$
$x$ $l$ $r$

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

また入力は全て整数で与えられ、以下の制約を満たす
$1\leq N \leq 100,000$
$1\leq Q \leq 100,000$
$0\leq x \leq 2$
$0\leq l \leq r \leq N-1$

出力

チームAのスコアとチームBのスコアを空白区切りで出力してください。最後に改行してください。

チームAのスコア チームBのスコア

サンプル

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

配列は次の様に遷移します。

[-----]
[AAAA-]
[AABBB]

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

配列は次の様に遷移します。

[-----]
[AAAAA]
[ABBBA]
[ABBBA] Bonus! A +1

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

配列は次の様に遷移します。

[------]
[-AA---]
[-AA-BB]
[-AA-BB] Bonus!
[BBBBBB]
[BAAAAA]
[BAAAAA] Bonus! A +5
最初のボーナスチャンスでは、$A_{2,4} = B_{2,4} = 1$なのでどちらにもボーナスポイントは入りません。
2回目のボーナスチャンスでは、$A_{0,5} = 5 > B_{0,5} = 1$ なのでAに5のボーナスポイントが与えられます。

提出ページヘ