Station <<Sorting>>
InterviewTime limit2sMemory limit512 MB
Given n distinct masses in a row, you may swap two adjacent cars only when their total mass is at most M; decide whether sorting by increasing mass is reachable.
- Level
Medium6 of 10
- Topics
- Sorting, Greedy, Array, Two pointers
- Solved
- No attempts yet
Problem
At the railway station <> there are freight cars on a track, and a train must be assembled from them. All cars have the same length, but they carry different cargo, so their masses can differ. The workers at station <> must line the cars up in increasing order of mass; only then is the train allowed to depart.
Usually shunting diesel locomotives and electric locomotives are used for this, but this station is testing an experimental car-sorting device. It is expected to cut the time needed to assemble trains substantially.
This hovercraft device moves above the cars, and its length is slightly greater than the length of two cars. It can hover over two adjacent cars, lift both into the air, and swap them. However, the device's load capacity is limited: it can perform this operation only when the total mass of the two cars does not exceed .
Your task is to write a program that determines whether the experimental car-sorting device can arrange the cars on the track in the required order.
Input
The first line of the input file contains two numbers: the number of cars () and the load capacity of the experimental device (). The second line of the input file contains the masses of the cars , \ldots, (these masses satisfy , and in addition the masses of the cars are pairwise distinct). The masses of the cars are listed in the input file in the order in which the cars initially stand on the track.
Output
Output the word <<Yes>> to the output file if the experimental car-sorting device can arrange the cars in the required order, and the word <<No>> otherwise.