Stairway to the Skyline
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
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".
Brain Booster #7
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 8
- Start at
- 2024-11-05 14:30
- End at
- 2024-11-05 16:45
- Duration
- 2.2 hour(s)
- Host
- Partic.
- 142