Overview

This problem requires you to record the guest numbers as they arrive and, for each query, determine whether a given number has “already arrived.”
It can be solved by choosing a data structure that efficiently supports insertion and membership checking.

Analysis

There are up to \(Q \le 4 \times 10^5\) operations, and guest numbers \(X_i\) can be as large as \(10^9\).

A naive approach would be: - Store the guest list in an array (list) and search from the beginning for each query.

This takes \(O(N)\) per membership check. In the worst case, with many queries, the total becomes \(O(Q^2)\), which is too slow for \(4 \times 10^5\) (TLE).

The key observations are as follows: - We only need “insertion” and “membership checking” (no deletion). - Since guest numbers can be very large, we cannot use a direct-indexed array (occurrence array) keyed by the number. - We want to make membership checking fast.

A typical solution that fits these conditions is to use a set. Python’s set uses hashing, allowing insertion and lookup in \(O(1)\) on average.

(Example) - Operation: 1 10 → Add {10} to the set - Operation: 2 10 → 10 in set is true, so output Yes - Operation: 2 5 → 5 in set is false, so output No

Algorithm

1. Prepare an empty set s.
2. Process each operation \((T_i, X_i)\) in order.
   • If \(T_i = 1\) (insertion), perform s.add(X_i).
   • If \(T_i = 2\) (query), check X_i in s. If it is contained, append Yes to the output; otherwise, append No.
3. Output all query results together in the order of operations.

Complexity

• Time complexity: \(O(Q)\) on average (each operation is \(O(1)\) on average)
• Space complexity: \(O(N)\) (where \(N\) is the number of recorded arrivals, at most \(O(Q)\))

Implementation Notes

• Since the input can be as large as \(4 \times 10^5\) lines, it is safer to use fast input via sys.stdin.buffer.read().

• Rather than calling print for each query, it is faster to accumulate results in an array out and output them all at once at the end.

• According to the problem statement, when \(T_i=1\), it is guaranteed that the same number does not already exist, so there is no need for a duplicate check during insertion.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    Q = int(next(it))
    s = set()
    out = []
    for _ in range(Q):
        t = int(next(it))
        x = int(next(it))
        if t == 1:
            s.add(x)
        else:
            out.append("Yes" if x in s else "No")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.