Overview

Each speech flips the support of a specified student between T and A, so we incrementally update the supporter counts and find the first speech number at which either supporter count reaches \(0\).

Analysis

The key observation is that “each speech changes the support of only one person.” This means we don’t need to recount everyone’s support after every speech.

• Naive approach: For each speech, scan the entire string \(S\) to count the number of Ts and As. This takes \(O(N)\) per check, and \(O(NM)\) overall, which at maximum is \(2\times 10^5 \times 2\times 10^5\) — far too large and will result in TLE.
• Improved approach: Count the initial number of T supporters \(t\_cnt\) and A supporters \(a\_cnt\) upfront, then for each speech, only update by the change from flipping student \(R_i\)’s support (\(+1\) / \(-1\)).

For example, if at some point \(t\_cnt=3, a\_cnt=2\) and a T supporter flips, then \(t\_cnt\) becomes \(2\) and \(a\_cnt\) becomes \(3\). In this way, updating just “the one person who changed” is sufficient, and each speech can be processed in \(O(1)\).

Also, note that the election result check happens “only immediately after each speech,” so we do not check at the initial state (though the constraints guarantee both sides have at least \(1\) person initially).

Algorithm

1. Count the initial number of T supporters \(t\_cnt\) from string \(S\). Set \(a\_cnt = N - t\_cnt\).
2. Process speeches \(i=1..M\) in order:
   • Check the current support of the specified student \(r=R_i\) (converted to \(0\)-indexed).
   • If T, flip to A, and update \(t\_cnt--, a\_cnt++\).
   • If A, flip to T, and update \(a\_cnt--, t\_cnt++\).
   • After the update, if \(t\_cnt==0\) or \(a\_cnt==0\), the election is decided at this point, so output \(i\) and terminate.
3. If neither count reaches \(0\) by the end, output -1.

Complexity

• Time complexity: \(O(N + M)\) (initial counting is \(O(N)\), each speech is \(O(1)\))
• Space complexity: \(O(N)\) (to store the support state \(S\))

Implementation Notes

• Since each speech requires knowing “which side that student currently supports,” we must also update \(S\) itself by flipping the value (without this, cases where a student is specified multiple times will break).

• In Python, for optimization, reading all input at once with sys.stdin.buffer.read() and using a bytearray to directly modify T/A values provides stable performance.

• Don’t forget that execution should terminate immediately the moment the election is decided (subsequent speeches are not carried out).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    M = int(data[1])
    S = bytearray(data[2])

    T = ord('T')
    A = ord('A')

    t_cnt = S.count(T)
    a_cnt = N - t_cnt

    for i in range(M):
        r = int(data[3 + i]) - 1
        if S[r] == T:
            S[r] = A
            t_cnt -= 1
            a_cnt += 1
        else:
            S[r] = T
            a_cnt -= 1
            t_cnt += 1

        if t_cnt == 0 or a_cnt == 0:
            sys.stdout.write(str(i + 1))
            return

    sys.stdout.write("-1")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.