B - ゲストリストの管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は、大規模なパーティーの受付係を担当することになりました。

パーティーには招待客が次々と到着します。各招待客には 1 以上 10^9 以下の整数からなる招待客番号が割り振られており、異なる招待客には異なる番号が割り振られています。高橋君は到着した人をゲストリストに記録していきます。また、会場のスタッフから「この人は既に到着していますか？」という問い合わせを受けることもあります。

ゲストリストは最初は空の状態です。

高橋君は Q 回の操作を順に行います。i 番目の操作は種類 T_i と招待客番号 X_i の組で表され、以下の 2 種類のいずれかです：

  • T_i = 1（到着の記録）：招待客番号 X_i の人物をゲストリストに追加する。ただし、この操作が行われる時点で X_i が既にゲストリストに含まれていないことが保証される。
  • T_i = 2（到着確認の問い合わせ）：招待客番号 X_i の人物が現在のゲストリストに含まれているかを調べる。

T_i = 2 である各操作について、指定された招待客番号を持つ人物がゲストリストに含まれているかどうかを判定してください。

制約

  • 1 \leq Q \leq 4 \times 10^5
  • T_i \in \{1, 2\}
  • 1 \leq X_i \leq 10^9
  • T_i = 1 である操作において、その時点で既に X_i がゲストリストに含まれていることはない
  • T_i = 2 である操作は少なくとも 1 回は存在する
  • 入力はすべて整数

入力

Q
T_1 X_1
T_2 X_2
\vdots
T_Q X_Q

1 行目には、操作の回数を表す整数 Q が与えられる。

続く Q 行のうち i 行目 (1 \leq i \leq Q) には、i 番目の操作の種類を表す整数 T_i と、招待客番号を表す整数 X_i がスペース区切りで与えられる。

出力

T_i = 2 である各操作について、操作が行われた順に結果を 1 行ずつ出力せよ。

招待客番号 X_i を持つ人物がその時点のゲストリストに含まれていれば Yes を、含まれていなければ No を出力せよ。

入力例 1

5
1 10
2 10
2 3
1 3
2 3

出力例 1

Yes
No
Yes

入力例 2

7
2 100
1 50
2 50
1 100
2 100
2 75
2 50

出力例 2

No
Yes
Yes
No
Yes

入力例 3

12
1 8
1 100
2 8
2 9
1 999999937
2 999999937
1 42
2 100
2 42
2 1000000000
1 1000000000
2 1000000000

出力例 3

Yes
No
Yes
Yes
Yes
No
Yes

入力例 4

24
2 500
1 500
1 123456789
2 1
2 500
1 1
2 1
1 999999999
2 123456789
2 999999998
1 777777777
1 250000000
2 777777777
2 250000000
2 100
1 100
2 100
1 314159265
2 314159265
2 271828182
1 271828182
2 271828182
2 999999999
2 123456

出力例 4

No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No

入力例 5

1
2 1000000000

出力例 5

No

Score : 300 pts

Problem Statement

Takahashi has been assigned as the receptionist for a large party.

Invited guests arrive at the party one after another. Each guest is assigned a guest number, which is an integer between 1 and 10^9 inclusive, and different guests are assigned different numbers. Takahashi records each arriving person on the guest list. He may also receive inquiries from the venue staff asking, "Has this person already arrived?"

The guest list is initially empty.

Takahashi performs Q operations in order. The i-th operation is represented by a pair of type T_i and guest number X_i, and is one of the following two types:

  • T_i = 1 (Record arrival): Add the person with guest number X_i to the guest list. It is guaranteed that X_i is not already in the guest list at the time this operation is performed.
  • T_i = 2 (Arrival inquiry): Check whether the person with guest number X_i is currently in the guest list.

For each operation where T_i = 2, determine whether the person with the specified guest number is in the guest list.

Constraints

  • 1 \leq Q \leq 4 \times 10^5
  • T_i \in \{1, 2\}
  • 1 \leq X_i \leq 10^9
  • For operations where T_i = 1, X_i is not already in the guest list at that time
  • There is at least one operation where T_i = 2
  • All input values are integers

Input

Q
T_1 X_1
T_2 X_2
\vdots
T_Q X_Q

The first line contains an integer Q representing the number of operations.

Of the following Q lines, the i-th line (1 \leq i \leq Q) contains an integer T_i representing the type of the i-th operation and an integer X_i representing the guest number, separated by a space.

Output

For each operation where T_i = 2, output the result on a separate line in the order the operations are performed.

If the person with guest number X_i is in the guest list at that time, output Yes; otherwise, output No.

Sample Input 1

5
1 10
2 10
2 3
1 3
2 3

Sample Output 1

Yes
No
Yes

Sample Input 2

7
2 100
1 50
2 50
1 100
2 100
2 75
2 50

Sample Output 2

No
Yes
Yes
No
Yes

Sample Input 3

12
1 8
1 100
2 8
2 9
1 999999937
2 999999937
1 42
2 100
2 42
2 1000000000
1 1000000000
2 1000000000

Sample Output 3

Yes
No
Yes
Yes
Yes
No
Yes

Sample Input 4

24
2 500
1 500
1 123456789
2 1
2 500
1 1
2 1
1 999999999
2 123456789
2 999999998
1 777777777
1 250000000
2 777777777
2 250000000
2 100
1 100
2 100
1 314159265
2 314159265
2 271828182
1 271828182
2 271828182
2 999999999
2 123456

Sample Output 4

No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No

Sample Input 5

1
2 1000000000

Sample Output 5

No