Overview

This problem asks us to efficiently count, for each of the \(N\) mountains, the number of mountains with strictly higher elevation.

Analysis

Naive Approach and Its Issues

The simplest method is to compare each mountain \(i\) with all other mountains by elevation.

for i in range(N):
    count = 0
    for j in range(N):
        if A[j] > A[i]:
            count += 1

This method takes \(O(N^2)\) time. When \(N\) is at most \(2 \times 10^5\), this requires \(4 \times 10^{10}\) comparisons, which won’t finish within the time limit (TLE).

Key Insight

“The number of mountains higher than oneself” can be rephrased as “the count of values in the entire array that are greater than one’s own elevation.”

If we sort the array beforehand, we can use binary search to quickly find “the count of elements greater than a certain value.”

Concrete Example

Consider elevations \([3, 1, 4, 1, 5]\).

After sorting, we get \([1, 1, 3, 4, 5]\).

• Mountain 1 (elevation 3): 2 mountains higher than 3, which are \([4, 5]\)
• Mountain 2 (elevation 1): 3 mountains higher than 1, which are \([3, 4, 5]\)
• Mountain 3 (elevation 4): 1 mountain higher than 4, which is \([5]\)
• Mountain 4 (elevation 1): 3 mountains higher than 1, which are \([3, 4, 5]\)
• Mountain 5 (elevation 5): 0 mountains higher than 5

The answer is \([2, 3, 1, 3, 0]\).

Algorithm

1. Sort the array: Create a sorted array sorted_A from the original array \(A\)
2. Find counts using binary search: For each mountain’s elevation \(a\)
   • Use bisect_right(sorted_A, a) to find “the count of elements less than or equal to \(a\)”
   • Subtract this value from \(N\) to get “the count of elements greater than \(a\)”

How bisect_right Works

bisect_right(sorted_A, a) returns the position where \(a\) would be inserted in the sorted array, placing it to the right of any existing elements equal to \(a\).

In other words, it returns the count of elements less than or equal to \(a\).

Example: When sorted_A = [1, 1, 3, 4, 5] - bisect_right(sorted_A, 3) → 3 (3 elements at positions 0, 1, 2 are ≤ 3) - Therefore, the count of elements greater than 3 is \(5 - 3 = 2\)

Complexity

• Time Complexity: \(O(N \log N)\)

  • Sorting: \(O(N \log N)\)
  • Binary search for each element: \(O(\log N) \times N = O(N \log N)\)

• Space Complexity: \(O(N)\)

  • Required for storing the sorted array and result array

Implementation Notes

1. Why use bisect_right: Since mountains with the same elevation are not included in “strictly higher,” we use bisect_right to find the count of elements “less than or equal to.” Using bisect_left would give the count of elements “strictly less than,” which would incorrectly count mountains with the same elevation as “higher.”

2. Preserve original order: Sorting is done on a separate array, keeping the original array \(A\) unchanged. This is because the output must follow the input order.

3. Fast I/O: To handle large \(N\), we use sys.stdin.readline to speed up input.

Source Code

import sys
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    
    # Create a sorted array
    sorted_A = sorted(A)
    
    # For each mountain, find the number of mountains with strictly higher elevation
    result = []
    for a in A:
        # Use bisect_right to find the count of elements <= a
        # N - bisect_right(sorted_A, a) gives the count of elements > a
        count = N - bisect_right(sorted_A, a)
        result.append(count)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.