Overview

Given test scores of \(N\) students, for each of \(Q\) queries, compare the scores of two specified students and determine whether the former’s score is strictly higher.

Analysis

This problem is a simple one that only requires referencing and comparing elements of an array.

Key observations: - Each query is independent and can be solved by simply comparing two scores - “Strictly higher” means \(S_{a_i} > S_{b_i}\); if they are equal (\(S_{a_i} = S_{b_i}\)), the answer is No - Comparisons between the same student (\(a_i = b_i\)) can also occur, but in this case \(S_{a_i} = S_{b_i}\) obviously holds, so the answer is No

Why a naive approach is sufficient: - Each query only accesses two elements of the array, so a single query can be processed in \(O(1)\) - Even with up to \(Q \leq 10^5\) queries, the total \(O(Q)\) is fast enough

Algorithm

1. Read the number of students \(N\) and the number of queries \(Q\)
2. Store the test scores of \(N\) students in an array \(H\)
3. For each query \((a_i, b_i)\):
   • Compare \(H[a_i - 1]\) and \(H[b_i - 1]\) (subtract 1 since the array is 0-indexed)
   • Output Yes if \(H[a_i - 1] > H[b_i - 1]\), otherwise output No

Concrete example (sample input):

3 4
80 90 70
2 1
1 3
3 2
1 1

• Student 1: 80 points, Student 2: 90 points, Student 3: 70 points
• Query 1: Student 2 (90 points) > Student 1 (80 points)? → Yes
• Query 2: Student 1 (80 points) > Student 3 (70 points)? → Yes
• Query 3: Student 3 (70 points) > Student 2 (90 points)? → No
• Query 4: Student 1 (80 points) > Student 1 (80 points)? → No (same student, so they are equal)

Complexity

• Time complexity: \(O(N + Q)\)
  • \(O(N)\) for reading the scores
  • \(O(Q)\) for processing each of the \(Q\) queries in \(O(1)\)
• Space complexity: \(O(N + Q)\)
  • \(O(N)\) for the array storing the scores
  • \(O(Q)\) for the list storing the results

Implementation Notes

• 1-indexed to 0-indexed conversion: The problem uses student numbers starting from 1 (1-indexed), but Python arrays start from 0 (0-indexed), so we access elements using H[a - 1] by subtracting 1

• Output optimization: Calling print() for each query can be slow, so we accumulate results in a list and output them all at once using '\n'.join(results) at the end

• Input optimization: Using sys.stdin.readline allows for fast reading of large amounts of input

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    H = list(map(int, input().split()))
    
    results = []
    for _ in range(Q):
        a, b = map(int, input().split())
        if H[a - 1] > H[b - 1]:
            results.append("Yes")
        else:
            results.append("No")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

This editorial was generated by claude4.5opus.