Задача №114653. Лифт
Дима работает в диспетчерской. В конце рабочего дня, когда он уже собирался уходить домой, ему поступил новый вызов. «Алло, вы нас слышите? Мы застряли в лифте, вытащите нас отсюда!». Теперь Диме нужно как можно скорее вызвать бригаду в соответствующий дом.
Для вызова бригады Диме нужно понять, на каком этаже застрял лифт. К сожалению, в доме, в который надо вызвать бригаду, лифт очень старый и не оснащён никакими датчиками. У Димы есть только данные о перемещениях лифта, записанные в один файл. Когда-то давно диспетчерская начала записывать, на сколько этажей лифт поднялся или опустился, при этом неизвестно, на каком этаже находился лифт, когда компания начала вести эти записи. Разумеется, лифт не мог подниматься выше этажа с номером \(h\) или опускаться ниже этажа с номером \(1\). Имея только эту информацию, не всегда можно точно определить, где находится лифт, поэтому для начала Дима хочет узнать, на скольких этажах лифт сейчас может находиться, если верить имеющемуся файлу.
Дима уже выключил свой компьютер и едет к застрявшим пассажирам, поэтому просит вас обработать файл за него.
В первой строке содержатся два целых числа \(n\) и \(h\) (\(1 \le n \le 100\,000\), \(2 \le h \le 10^{12}\)) — количество строк в файле Димы и количество этажей в доме, соответственно.
В следующих \(n\) строках содержатся записи о перемещениях лифта, \(i\)-я запись которого вводится в одном из следующих форматов:
- u x — означает, что лифт поднялся вверх на \(x\) этажей (\(1 \le x < h\)).
- d x — означает, что лифт спустился вниз на \(x\) этажей (\(1 \le x < h\)).
Записи в логе даны в хронологическом порядке, последняя запись соответствует перемещению, после которого лифт застрял. Известно, что последнее перемещение лифт проделал полностью, то есть невозможна ситуация, в которой в логе записано, например, перемещение вверх на два этажа, однако лифт проехал вверх один этаж и застрял.
Выведите одно число — количество этажей, на которых может находиться лифт. Если входные данные противоречивы и не могут соответствовать действительности, выведите « 0 » (без кавычек).
В первом тесте лифт может находиться на этажах 3 и 4, которым бы соответствовали такие перемещения: \(\)1 \rightarrow 2 \rightarrow 4 \rightarrow \textbf{3},\ 2 \rightarrow 3 \rightarrow 5 \rightarrow \textbf{4}\(\)
Если же лифт изначально находился выше второго этажа, то он не мог подняться на 3 этажа, потому что уперся бы в потолок.
Во втором тесте подъем на \(20\) этажей суммарно невозможен.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | |||||
| Группа | Баллы | \(n\) | \(h\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 20 | \(n \leq 1000\) | \(h \leq 1000\) | – | Лифт двигался только вверх. |
| 2 | 15 | \(n \leq 1000\) | \(h \leq 1000\) | 0, 1 | |
| 3 | 42 | \(n \leq 100\,000\) | \(h \leq 100\,000\) | 0, 1, 2 | |
| 4 | 23 | – | – | 0, 1, 2, 3 | |
3 5 u 1 u 2 d 1
2
2 11 u 10 u 10
0