この問題はサンプルです
注意
必ずお読みください
マルチテストについて
当コンテスト (TGC002, TGC003) では全ての問題で「マルチテスト」形式が採られています.
この形式の問題では,一つのテストファイルに対して複数のテストケースが与えられます.
このことは,本番の各問題で改めて注記しません.
当サンプル問題を用いてご確認ください.
制約の特殊な表記について
なお,簡単のために,制約の表示について独自の略記を用いることがあります.
各表記の意味を以下に示します:
- Φ:テストケース数を表す定数です.テストファイルの(絶対的な)最初の行で与えられます.
- Φϕ(X):ϕ 番目のテストケースで与えられる,問題文中の定数 X の値を表します.
- ∑ϕ:1≤ϕ≤Φ∑ の略記です.
入力について
テストファイル全体を通して,入力は標準入力から次のように与えられます:
casek は k 番目のテストケースです.
これは必ずしも 1 行であるとは限りません.
出力について
テスト全体を通して,出力は標準出力へ次のように出力してください:
outputk は k 番目のテストケースに対する出力です.
これは必ずしも 1 行であるとは限りません.
入出力の高速化について
サンプル・本番を問わず,いずれの問題においてもかなりの量の入出力が行われます.
ご使用の言語によらず,可能ならば高速な方法での標準入出力を行うことを推奨します.
以上の内容は,当サンプル問題や本番の各問題を含めて全ての問題で共通です.
問題文
1 から 109 までの番号によって区別された 109 本の毛穴があります.
はじめ,すべての毛穴には髪の毛が 1 本,コンテストが 0 個生えています.
Q 個のイベントが順に起こりました.
k(1≤k≤Q) 番目のイベントは以下です:
- tk=0 のとき:毛穴 xk に髪の毛が生えているならば,その髪の毛が抜け,髪の毛跡地となる.そうでなければ何も起こらない.
- tk=1 のとき:毛穴 xk 毛穴が髪の毛跡地であるならば,そこにコンテストが 1 つ生える.そうでなければ何も起こらない.
いずれの毛穴に対しても,任意の個数のコンテストが生え得ます.
Q 個すべてのイベントが起こったあと,合計でいくつのコンテストが生えていますか?
求めてください.
制約
- 1≤Φ≤105
- ※一つのテストファイルで与えられるテストケースの個数が 1 以上 105 以下であることを示します.
- 1≤Q
- ※各テストケースについて,Q の値が 1 以上であることを示します.
- ∑ϕΦϕ(Q)≤105
- ※Φ 個全てのケースにおける Q の値の総和が 105 以下であることを示します.
- tk∈{0,1}(1≤k≤Q)
- ※各テストケースについて,tk の値が 0 または 1 であることを示します.
- 1≤xk≤109(1≤k≤Q)
- ※各テストケースについて,xk の値が 1 以上 109 以下であることを示します.
入力
各テストケースの入力は,それぞれ以下の形式で与えられる:
出力
答えを出力せよ.
サンプル
入力例1
1
7
0 1
0 2
1 1
1 3
0 1
1 2
1 1
- 1 つ目のイベントでは,毛穴 1 の髪の毛が抜け,髪の毛跡地になります.
- 2 つ目のイベントでは,毛穴 2 の髪の毛が抜け,髪の毛跡地になります.
- 3 つ目のイベントでは,毛穴 1 にコンテストが 1 つ生えます.
- 4 つ目のイベントでは,何も起こりません.
- 5 つ目のイベントでは,何も起こりません.
- 6 つ目のイベントでは,毛穴 2 にコンテストが 1 つ生えます.
- 7 つ目のイベントでは,毛穴 1 にコンテストがもう 1 つ生えます.
入力例2
2
1
1 1
3
1 1
0 1
0 1