Stairway to the Skyline
Time Limit: 1.0 s
Memory Limit: 512.0 MB
Description
Mike, a dreamer, recently visited a city called Wonderland, known for its towering skyscrapers. He wondered if he could rearrange a contiguous segment of buildings to form a "staircase" — a sequence where each building's height is at least as tall as the previous one.
Mike recorded the heights of n
buildings in order as he walked through the city. He wants to find out if it is possible to select a single contiguous segment of at most k
buildings and reorder that segment to create the staircase. The buildings are numbered from 1
to n
.
Given the heights of the building, determine if there exists a segment of no more than k
consecutive buildings that can be rearranged to form a staircase. If multiple such segments exist, output the leftmost smallest range. If it is not possible to form the staircase, output "NO". You can safely assume the the skycrapers does not form a staircase initially.
Format
Input
- An integer
n
: the number of buildings. - An integer
k
: the maximum number of consecutive buildings Mike can reorder. - An array of
n
integers representing the heights of each building in sequence.
Constraints
\(2 <= n, k <= 10^5\)
\(1 <= h[i] <= 10^9\)
Output
- If a suitable segment exists, output
YES
, followed by a new line indicating the smallest possible rangel r
- If no such segment exists, output
NO
.
Sample 1
Input
5 2
1 2 4 3 5
Output
YES
3 4
Sample 2
Input
5 2
1 4 2 3 5
Output
NO
Explanation
In the first test case of sample 1, you can select the segment from positions 3 to 4 (heights: 4, 3). By reordering these 2 elements, you can create the non-decreasing sequence: (3, 4).
In the second test case of sample 2, the smallest segment to reorder is from positions 2 to 4 (heights: 4, 2, 3), which requires reordering 3 elements, exceeding the limit of k
, thus the output is "NO".
Information
- ID
- 1120
- Difficulty
- 4
- Category
- (None)
- Tags
- (None)
- # Submissions
- 160
- Accepted
- 42
- Accepted Ratio
- 26%
- Uploaded By