Overview

For each round, determine whether “the highest-scoring player scored at least \(2\) times the highest score among all other players,” and count the number of such rounds.

Analysis

The condition for player \(i\) to be dominant in round \(j\) is: \(S_{j,i} \ge 2 \times M_{j,i}\) (where \(M_{j,i}\) is the maximum score among “all players except player \(i\)”).

The key observations are the following two points:

1. If there is a dominant player, that player must be the sole leader of that round. If multiple players share the highest score, then the maximum value excluding a given player \(M_{j,i}\) would also equal that highest score, and \(S_{j,i} \ge 2 \times M_{j,i}\) would require \(S_{j,i} \ge 2S_{j,i}\), which cannot hold. Therefore, the highest score must be unique (held by exactly one player).

2. If the highest score is unique, “the maximum among all others” is simply the second largest value. Let \(max1\) be the highest score and \(max2\) be the second highest. When the highest score is unique, \(M_{j,i} = max2\). Therefore, the check reduces to:

   • The highest score is unique (appears exactly once)
   • \(max1 \ge 2 \times max2\)

These two conditions are sufficient.

Naively computing \(M_{j,i}\) for each player \(i\) could result in \(O(N^2)\) computation per round, which is too slow. However, by only tracking the maximum and the second maximum for each round, we can perform the check in \(O(N)\).

Example: If the scores are [10, 3, 4, 2], \(max1=10, max2=4\), so there is a sole leader and \(10 \ge 2\times 4=8\), making this a “dominant round.” On the other hand, [10, 5, 4] gives \(max1=10, max2=5\), and \(10 \ge 10\) holds, so it’s OK. [10, 10, 1] has two players sharing the highest score, so it is not unique — NG.

Algorithm

For each round, do the following:

1. While reading the scores of that round from left to right, maintain:
   • The maximum value \(max1\)
   • The second maximum value \(max2\)
   • The number of occurrences of the maximum \(cnt1\)
2. After reading all scores for the round, if:
   • \(cnt1 == 1\) (the maximum is unique)
   • \(max1 \ge 2 \times max2\)

then increment the answer by \(+1\).

Update procedure (each time a value \(x\) is read): - \(x > max1\): \(max2 \leftarrow max1\), \(max1 \leftarrow x\), \(cnt1 \leftarrow 1\) - \(x == max1\): \(cnt1 \leftarrow cnt1 + 1\) - \(max2 < x < max1\): \(max2 \leftarrow x\)

This allows us to determine the result by scanning each round only once.

Complexity

• Time complexity: \(O(NT)\) (just a single pass over all input. Since the constraint is \(NT \le 10^6\), this is sufficiently fast.)
• Space complexity: \(O(1)\) (only a constant number of variables — maximum, second maximum, count, etc. — are maintained per round.)

Implementation Notes

• Whether the maximum is unique is crucial, so be sure to count the number of occurrences \(cnt1\) of the maximum.

• Since the input can contain up to \(10^6\) integers, in Python it is advisable to use fast input via sys.stdin.buffer.read() for stability (the provided code manually parses integers from a byte string).

• The initial value of \(max2\) can be \(-1\) or any sufficiently small value (since scores are at least \(1\), this causes no issues).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read()
    n = len(data)
    idx = 0

    def read_int():
        nonlocal idx
        while idx < n and data[idx] <= 32:
            idx += 1
        val = 0
        while idx < n and data[idx] > 32:
            val = val * 10 + (data[idx] - 48)
            idx += 1
        return val

    N = read_int()
    T = read_int()

    ans = 0
    for _ in range(T):
        max1 = -1
        max2 = -1
        cnt1 = 0
        for _ in range(N):
            x = read_int()
            if x > max1:
                max2 = max1
                max1 = x
                cnt1 = 1
            elif x == max1:
                cnt1 += 1
            elif x > max2:
                max2 = x
        if cnt1 == 1 and max1 >= 2 * max2:
            ans += 1

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.