Overview

This is a problem where you process events that flip students’ support states in order, and find the first time when one of the candidates has \(0\) supporters.

Analysis

Each time a speech is given, a student’s support state changes. However, if you check all students’ support states every time and recount the number of supporters for Takahashi and Aoki, each check takes \(O(N)\) time. Repeating this \(M\) times results in an overall complexity of \(O(NM)\), which exceeds the time limit (TLE) under the given constraints (\(N, M \leq 2 \times 10^5\)).

To solve this, we take the approach of maintaining the total supporter counts as variables and only updating them by the difference when a change occurs.

For example, suppose a student’s support changes from “Takahashi (T)” to “Aoki (A)”. In this case, the overall supporter counts change as follows: - Takahashi’s supporter count: decreases by \(1\) - Aoki’s supporter count: increases by \(1\)

In this way, if we only add \(+1\) or \(-1\) to two variables per speech, each operation completes in \(O(1)\). Then, by simulating while updating an array that records which candidate each student currently supports, we can efficiently find the answer.

Algorithm

1. Convert the initial state string \(S\) into a mutable array (list) of characters.
2. Count the initial number of Takahashi’s supporters t_count and Aoki’s supporters a_count.
3. For each of the \(M\) speeches, perform the following operations in order:
   • Check the current support state of the target student \(R_i\).
   • If T: change the array value to A, decrease t_count by \(1\), and increase a_count by \(1\).
   • If A: change the array value to T, decrease a_count by \(1\), and increase t_count by \(1\).
   • Immediately after the change, check whether t_count or a_count has become \(0\). If so, output the current speech number (\(i\)-th speech) and terminate the program.
4. If neither supporter count reaches \(0\) after all \(M\) operations, output \(-1\).

Complexity

• Time complexity: \(O(N + M)\)
  • Counting the initial state and creating the array takes \(O(N)\).
  • Each speech operation can be done in \(O(1)\), so \(M\) operations take \(O(M)\).
  • Therefore, the overall complexity is \(O(N + M)\), which is sufficiently fast.
• Space complexity: \(O(N + M)\)
  • The array managing students’ support states uses \(O(N)\) memory.
  • The list for reading all input data at once uses \(O(N + M)\) memory.

Implementation Notes

• String mutability (immutability) Python strings (str type) do not allow direct modification of individual characters (e.g., S[0] = 'A' raises an error). Therefore, you need to first convert the string to a list of characters using list(S).

• Index adjustment (0-indexed vs 1-indexed) The student numbers \(R_i\) given in the input start from \(1\) (1-indexed), but Python array indices start from \(0\) (0-indexed). When accessing the array, be careful to subtract \(1\) from the input value and use idx = R_i - 1.

• Fast input/output Since the input data is large, using sys.stdin.read().split() to read all input at once reduces the time spent on input/output.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    S = input_data[2]
    
    state = list(S)
    t_count = S.count('T')
    a_count = N - t_count
    
    for i in range(M):
        idx = int(input_data[3 + i]) - 1
        if state[idx] == 'T':
            state[idx] = 'A'
            t_count -= 1
            a_count += 1
        else:
            state[idx] = 'T'
            a_count -= 1
            t_count += 1
            
        if t_count == 0 or a_count == 0:
            print(i + 1)
            return
            
    print(-1)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.