Подразделы

Другие разделы

Дата и время

24/11/2024 02:59:33

Авторизация

Зарегистрироваться
Восстановить пароль

2139. Television

Television Рис. 1

Television

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

The mayor has decided that it is high time to implement a new system of television transmitters. The city can be represented as a segment of the length D on which there are buildings of different heights. The width of a building is negligible. On top of some buildings, television transmitters are set, their dimensions are also negligible.

Television transmitters emit a television signal in all directions around them. The signal is spread through space in straight lines and cannot pass through buildings. A certain point in the city is considered covered if it is reached by a signal from an existing transmitter.

Find the segment of the city covered by television signal and output its length.

The first line of input contains the integer `N` (`1\ ≤\ N\ ≤\ 3*10^5`), the number of buildings, and the integer `D` (`1\ ≤\ D\ ≤\ 10^9`), the city length.

Each of the following `N` lines contains three numbers which describe the `i`th building:

a number which determines whether there is a transmitter on top of the building: 0 (no) or 1 (yes)
an integer `X_i` (`0\ ≤\ X_i\ ≤\ D`), the distance between the building and the left end of the city
an integer `H_i` (`1\ ≤\ H_i\ ≤\ 10^9`), the building height

The buildings are sorted in ascending order by the distance from the left end of the city. No two buildings will be located on the same distance from the left end of the city.

The first and only line of output must contain the required length from the text.

Note: the maximum permissible deviation from the official solution is `10^-3`.

Sample Input #1

Sample Output #1

6.000000

Sample Input #2

Sample Output #2

8.500000

Clarification of the second example: This example corresponds to the image from the text. The image depicts the city. The buildings are marked with vertical lines, and the transmitters with circles on the tops of the buildings. The bold lines on the x-axis represent the segment of the city not covered by television signal.