Overview

This problem involves managing a “guest list” that tracks invitation numbers, where you need to efficiently add new numbers and check whether a specific number is already in the list.

Analysis

The two operations required in this problem are: 1. Addition: Add a new element to the list. 2. Search: Determine whether a specific element is contained in the list.

Naive Approach

For example, consider managing the guest numbers using an “array (Python’s list)”. - Addition: Simply appending to the end of the array takes \(O(1)\). - Search: Since you need to search sequentially from one end of the array, in the worst case it takes \(O(N)\) time relative to the current number of elements \(N\) in the list.

If the total number of queries is \(Q\), the worst-case time complexity is \(O(Q^2)\). In this problem, \(Q = 4 \times 10^5\), so \(Q^2 \approx 1.6 \times 10^{11}\), which far exceeds the typical time limit (around 2 seconds), resulting in TLE (Time Limit Exceeded).

Efficient Approach

To perform searches efficiently, the optimal choice is to use a “set (Python’s set)”, a data structure based on a hash table. - Using a set, both addition and search can be performed in average \(O(1)\) time. - Although the guest number \(X_i\) can be as large as \(10^9\), a set only manages elements that actually exist, so memory usage is proportional to the number of added elements \(Q\), not the magnitude of \(X_i\).

Algorithm

1. Prepare an empty set guest_list.
2. For each query \((T_i, X_i)\), repeat the following process \(Q\) times:
   • When \(T_i = 1\): Add \(X_i\) to guest_list.
   • When \(T_i = 2\): Check whether \(X_i\) is contained in guest_list. If it is, store Yes in the output list; otherwise, store No.
3. After processing all queries, output the results all at once.

Complexity

• Time Complexity: \(O(Q)\)
  • Each addition and search operation takes average \(O(1)\), and repeating this \(Q\) times gives an overall complexity of \(O(Q)\).
• Space Complexity: \(O(Q)\)
  • At most \(Q\) guest numbers are stored in the set, so the memory usage is \(O(Q)\).

Implementation Notes

• Fast I/O: Since \(Q\) is as large as \(4 \times 10^5\), repeatedly using Python’s standard input() or print() may cause I/O to become a bottleneck.

  • Use sys.stdin.read().split() to read all input at once.
  • Combine sys.stdout.write() with "\n".join() to output all answers at once. These optimizations can significantly reduce execution time.

• Data Types: Values extracted from input_data can be inserted into the set as strings, and the search will work correctly as long as the same type (string to string) is used for comparison. In this code, conversion to integers is minimized for the sake of speed.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 操作回数 Q
    Q = int(input_data[0])
    
    # ゲストリストをセット(集合型)で管理 (追加・検索ともに平均O(1))
    guest_list = set()
    
    # 出力を高速化するためにリストに格納して最後にまとめて出力する
    results = []
    
    # 各操作を処理
    # input_data[1], input_data[2] が最初の操作の T_1, X_1
    for i in range(Q):
        t = input_data[1 + 2 * i]
        x = input_data[2 + 2 * i]
        
        if t == '1':
            # 操作1: ゲストリストに追加
            guest_list.add(x)
        else:
            # 操作2: ゲストリストに含まれているか確認
            if x in guest_list:
                results.append("Yes")
            else:
                results.append("No")
    
    # まとめて出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.