Задача C. Экскурсии
Задачу добавил: alef
Успешно сдано решений: 209
И министр науки Фалалей тоже с предложением выступил. Такое грандиозное строительство с самого своего начала должно стать туристическим объектом. И ежели известен план строительства — какие работы в какой день и час проводиться будут, то надо разработать и план экскурсий.
В будущем спортивно-туристическом комплексе можно выделить n площадок, на которых может быть интересно наблюдать за происходящим. Из-за пределов стройки можно попасть только на площадки #1 и #n. Перемещаться между площадками можно только последовательно, между каждой парой площадок с соседними номерами существует единственный безопасный проход: проход #i соединяет площадки #i и #(i + 1). Никаких других проходов, пригодных для экскурсантов, не существует.
Изначально все проходы считаются безопасными, а предлагаемый экскурсионный маршрут состоит из (n - 1) прохода. Ради краткости будем говорить, что маршрут имеет длину n - 1.
Однако на некоторых этапах строительства некоторые проходы могут стать небезопасными, и передвижение по ним будет временно запрещено. Разумеется, экскурсионный маршрут должен целиком и полностью состоять из безопасных проходов.
Со строителями существует договорённость, что в такие моменты будет организован временный доступ из-за пределов стройки ещё к одной-двум другим площадкам. В этом случае организаторы экскурсии изменят её начальную и / или конечную площадки и ограничатся более коротким экскурсионным маршрутом. Конечно, организаторы хотят, чтобы этот маршрут был как можно более длинным.
Ваша задача — по состоянию проходов определить максимально возможную длину экскурсионного маршрута.
В первой строке содержится целое число n (2 ≤ n ≤ 1001) — количество площадок.
Во второй строке содержится целое число q (1 ≤ q ≤ 3000) — количество запросов.
В каждой из следующих q строк содержится по одному запросу. Запрос может иметь следующий вид:
— проход #i считается опасным (i = 1, 2, ..., n - 1);
— проход #i считается безопасным (i = 1, 2, ..., n - 1);
w — запрос на вывод максимально возможной длины маршрута.
Гарантируется, что во входных данных присутствует по крайней мере один запрос на вывод максимально возможной длины маршрута.
Также гарантируется, что если некоторый проход объявляется опасным, то на момент объявления он был безопасным, и наоборот, если некоторый проход объявляется безопасным, то на момент объявления он был опасным.
Выведите ответы на запросы о максимально возможной длине маршрута по одному на строке.
Подзадача 1 (до 30 баллов)
n, q ≤ 100
Баллы начисляются за каждый пройденный тест.
Подзадача 2 (70 баллов)
n ≤ 1001, q ≤ 3000
Баллы начисляются при условии прохождения всей группы тестов.
По запросу сообщается результат проверки на каждом тесте.
Входные данные
8
33
w
d 3
w
d 7
w
d 5
w
s 3
w
d 2
w
d 1
w
d 3
w
d 6
w
d 4
w
s 3
w
s 6
w
s 7
w
s 5
w
s 1
w
s 2
w
s 4
w
7
4
3
2
4
2
2
1
1
0
1
1
2
3
3
3
7