問題一覧 > 通常問題

No.230 Splarraay スプラレェーイ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : koyumeishikoyumeishi
9 ProblemId : 625 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:29

問題文

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

ルール

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

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

入力

N
Q
x l r

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

また入力は全て整数で与えられ、以下の制約を満たす
1N100,000
1Q100,000
0x2
0lrN1

出力

チーム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
最初のボーナスチャンスでは、A2,4=B2,4=1なのでどちらにもボーナスポイントは入りません。
2回目のボーナスチャンスでは、A0,5=5>B0,5=1 なのでAに5のボーナスポイントが与えられます。

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