Страны Байтландия и Берляндия расположены на прямой $$$Ox$$$. Кроме этого на этой прямой расположены и спорные города, которые принадлежат каждой из стран по их мнению. Таким образом, на прямой $$$Ox$$$ расположены города трёх типов:
Недавно был запущен проект BNET — компьютерная сеть нового поколения. Теперь задача обоих государств соединить города так, чтобы сеть этой страны была связной.
Страны договорились соединить пары городов кабелями BNET таким образом, чтобы:
Таким образом, надо выбрать набор пар городов так, чтобы, соединив их, выполнялись оба условия одновременно. Кабели осуществляют двунаправленную передачу данных. Каждый кабель соединяет ровно два различных города.
Стоимость прокладки кабеля из одного города в другой равна расстоянию между городами. Найдите минимальную суммарную стоимость прокладки набора кабелей, чтобы два подмножества городов (Байтландии и спорных городов, Берляндии и спорных городов) были связны.
Каждый город является точкой на прямой $$$Ox$$$. Технически возможно соединить города $$$a$$$ и $$$b$$$ кабелем так, что город $$$c$$$ ($$$a < c < b$$$) не подключен к этому кабелю, где $$$a$$$, $$$b$$$ и $$$c$$$ — одновременно координаты городов $$$a$$$, $$$b$$$ и $$$c$$$.
В первой строке записано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — количество городов.
Далее следует $$$n$$$ строк, в каждой из которых задано целое число $$$x_i$$$ и буква $$$c_i$$$ ($$$-10^{9} \le x_i \le 10^{9}$$$) — координаты очередного города и его тип. Если город принадлежит Байтландии, то $$$c_i$$$ равно «B». Если город принадлежит Берляндии, то $$$c_i$$$ равно «R». Если город является спорным между странами, то $$$c_i$$$ равно «P».
Все города имеют различные координаты. Гарантируется, что города заданы в порядке увеличения их координат.
Выведите минимальную суммарную длину такого набора кабелей, что если удалить все города Берляндии ($$$c_i$$$=«R»), можно будет найти путь от любого оставшегося города до любого другого оставшегося города, двигаясь только по кабелям. Аналогично, если удалить все города Байтландии ($$$c_i$$$=«B»), можно будет найти путь от любого оставшегося города до любого другого оставшегося города, двигаясь только по кабелям.
4
-5 R
0 P
3 P
7 B
12
5
10 R
14 B
16 B
21 R
32 R
24
В первом примере нужно соединить первый город со вторым, второй с третьим, а третий с четвертым. Суммарная длина кабелей будет равна $$$5 + 3 + 4 = 12$$$.
Во втором примере нет спорных городов, поэтому нужно соединить все соседние города Байтландии и все соседние города Берляндии. Города Берляндии имеют координаты $$$10, 21, 32$$$, поэтому для их соединения нужно два кабеля длины $$$11$$$ и $$$11$$$. Города Байтландии имеют координаты $$$14$$$ и $$$16$$$, поэтому для их соединения нужен один кабель длины $$$2$$$. Таким образом, суммарная длина всех кабелей равна $$$11 + 11 + 2 = 24$$$.
Название |
---|