Overview

Given the positions of trees, the problem asks you to choose one interval \([L,R]\) of length at most \(K\) and find the maximum number of trees that fall within it.

Key Observations

• The number of trees in a given interval \([L,R]\) can be counted as a “contiguous portion (a range of consecutive indices)” when the coordinates are sorted in ascending order.
  In other words, if we sort the coordinates as \(X[0] < X[1] < \dots < X[N-1]\), the maximum number of trees in the interval equals “the maximum length of a range obtained by choosing some \(l,r\) such that \(X[r]-X[l]\le K\).”
• A naive approach of finding the maximum \(r\) satisfying the condition for every \(l\) (or trying all intervals) would be \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).
• The crucial observation is that “as the right endpoint \(r\) moves to the right, the left endpoint \(l\) required to satisfy the condition \(X[r]-X[l]\le K\) can only move to the right.”
  This allows us to process everything in \(O(N)\) using the Two Pointers (sliding window) technique, where both endpoints only move in one direction.

Example: \(X=[1,3,4,10,11]\), \(K=3\)
- Up to \(r=2\) (coordinate 4), the interval \([1,4]\) has length 3 and contains 3 trees.
- When \(r=3\) (coordinate 10), \(10-1=9>3\), so we advance the left endpoint until the condition is satisfied.
This property that “the left endpoint never moves back” is the key to the speedup.

Algorithm

1. Sort the coordinate array \(X\) in ascending order.
2. Initialize the left pointer \(l=0\) and the answer \(ans=0\).
3. Move the right pointer \(r\) from \(0\) to \(N-1\) in order:
   • While \(X[r]-X[l] > K\), increment \(l\) by \(1\) until the condition \(X[r]-X[l] \le K\) is satisfied.
   • At this point, the number of trees in the interval is \(r-l+1\), so update \(ans=\max(ans, r-l+1)\).
4. Output \(ans\).

After sorting, we are essentially finding “the maximum length of a contiguous subarray satisfying \(X[r]-X[l]\le K\).”

Complexity

• Time complexity: Sorting is \(O(N\log N)\) and the two pointers technique is \(O(N)\), so the overall complexity is \(O(N\log N)\).
• Space complexity: \(O(N)\) for the coordinate array, etc.

Implementation Notes

• Without sorting first, “trees within an interval” cannot be treated as a contiguous portion, making the two pointers technique inapplicable.

• Use something like while X[r] - X[l] > K: l += 1 to advance the left endpoint until the condition is satisfied (the key point is that it never moves back).

• Updating the answer simply involves computing r - l + 1 for each \(r\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = list(map(int, input().split()))
    X.sort()

    ans = 0
    l = 0
    for r in range(N):
        while X[r] - X[l] > K:
            l += 1
        ans = max(ans, r - l + 1)

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.