Overview

This problem requires recording the arrival of invited guests and quickly determining whether a specific guest has already arrived. We manage this efficiently using a set.

Analysis

Essence of the Problem

In this problem, we need to efficiently perform the following two operations: 1. Add operation: Add a guest number to the guest list 2. Search operation: Check whether a given guest number exists in the guest list

Issues with a Naive Approach

If we manage the guest list using a regular list (array): - Add operation: \(O(1)\) (append to the end) - Search operation: \(O(N)\) (linear search from the beginning of the list)

There are up to \(Q = 4 \times 10^5\) operations, and in the worst case, every search would require scanning all elements. If there are \(Q\) searches, this becomes \(O(Q^2)\), requiring approximately \(1.6 \times 10^{11}\) operations, resulting in TLE (Time Limit Exceeded).

Solution

By using a set, both add and search operations can be performed in average \(O(1)\) time.

Python’s set is implemented using a hash table, making membership checks extremely fast.

Concrete Example

Operation 1: T=1, X=100 → Guest list: {100}
Operation 2: T=1, X=200 → Guest list: {100, 200}
Operation 3: T=2, X=100 → 100 exists → "Yes"
Operation 4: T=2, X=300 → 300 does not exist → "No"

Algorithm

1. Prepare an empty set guest_set
2. Process \(Q\) operations in order:
   • When \(T_i = 1\): Add \(X_i\) to guest_set
   • When \(T_i = 2\): If \(X_i\) is contained in guest_set, add “Yes” to the output list; otherwise, add “No”
3. Output all query results together at the end

Complexity

• Time complexity: \(O(Q)\)

  • Each operation (add/search) runs in average \(O(1)\)
  • With \(Q\) operations, the overall complexity is \(O(Q)\)

• Space complexity: \(O(Q)\)

  • Up to \(Q\) guest numbers may be stored in the set
  • The output list also stores up to \(O(Q)\) results

Implementation Notes

1. Fast input: By using sys.stdin.readline, we can read large amounts of input quickly. This is faster than the standard input().

2. Batched output: Instead of calling print for each result one by one, we accumulate results in a list and output them all at once at the end using '\n'.join(results). This reduces the overhead of output operations.

3. Using the in operator: In Python, simply writing X in guest_set determines whether an element is contained in the set in \(O(1)\). For a list, this would take \(O(N)\), so the choice of data structure is crucial.

   Source Code

import sys

def main():
    input = sys.stdin.readline
    Q = int(input())
    guest_set = set()
    results = []
    
    for _ in range(Q):
        T, X = map(int, input().split())
        if T == 1:
            guest_set.add(X)
        else:  # T == 2
            if X in guest_set:
                results.append("Yes")
            else:
                results.append("No")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.