Задача №115208. Робот-пылесос
Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером \(k \times k\) со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке \((0, 0)\), а правый верхний, соответственно — в точке \((k, k)\).
Вам дана последовательность из \(n\) перемещений робота по плоскости, \(i\)-е перемещение характеризуется направлением \(d_i\), принимающим значения ' N ' (вверх, увеличение координаты \(Y\)), ' S ' (вниз, уменьшение координаты \(Y\)), ' W ' (влево, уменьшение координаты \(X\)) или ' E ' (вправо, увеличение координаты \(X\)), и целым числом \(a_i\) — расстоянием, на которое робот перемещается.
На рисунке приведены примеры возможных перемещений робота в каждом направлении.
Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера \(k \times k\), на котором находился робот.
По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.
В первой строке ввода через пробел даны два целых числа: размер робота \(k\) и количество команд \(n\) (\(1 \leq k \leq 10^4\); \(1 \leq n \leq 10^5\)).
В \(i\)-й из следующих \(n\) строк через пробел даны направление \(i\)-го перемещения \(d_i\) и его расстояние \(a_i\) (\(d_i\) — буква ' N ', ' S ', ' W ' или ' E '; \(1 \leq a_i \leq 10^9\)).
Выведите суммарную площадь убранной роботом поверхности.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 9 | \(k = 1\), \(n \le 10\), \(a_i \le 10\) | первая ошибка | |
| 2 | 10 | \(k \le 10\), \(n \le 10\), \(a_i \le 100\) | 1 | первая ошибка |
| 3 | 11 | \(k \le 1000\), \(n \le 1000\), \(a_i = 1\) | первая ошибка | |
| 4 | 8 | \(k \le 10^4\), \(n \le 10^5\), \(a_i = k\) | первая ошибка | |
| 5 | 14 | \(k = 1\), \(n \le 1000\), \(a_i \le 10^9\) | 1 | первая ошибка |
| 6 | 15 | \(k \le 10^4\), \(n \le 1000\), \(a_i \le 10^9\) | 1–3, 5 | первая ошибка |
| 7 | 16 | \(k = 1\), \(n \le 10^5\), \(a_i \le 10^9\) | 1, 5 | первая ошибка |
| 8 | 17 | \(k \le 10^4\), \(n \le 10^5\), \(a_i \le 10^9\) | 1–7 | первая ошибка |
Ниже приведены иллюстрации к перемещениям робота согласно примерам из условия. Клетки, которые робот посетил за время своих перемещений, затемнены.
1 5 E 2 N 2 W 4 S 4 E 4
17
3 4 W 2 N 1 W 1 N 2
27