0401. Дом Солнца

Девочка Саша очень любит солнце. В её треугольном доме практически нет окон, поэтому она хочет переехать в новый прямоугольный дом, в котором n окон на северной стороне и m окон на западной стороне (можно считать, что стороны дома ориентированы по сторонам света, при этом, если смотреть на план дома сверху, то верхняя сторона прямоугольника будет северной, а левая, соответственно, западной).

Для упрощения строительства Саша разметила свой дом (размерами R *C метров) на клетки 1 *1 метр. Таким образом она получила R строк и C столбцов. Саша располагает окна на северной стороне так, что каждое окно занимает целый отрезок столбцов (возможно, один столбец), то есть каждое окно имеет ширину равную целому количеству метров. Аналогично располагаются окна на западной стороне – каждое окно занимает целое количество строк.

Саша хочет знать, какая площадь её нового дома будет освещаться солнцем. При этом она считает, что Солнце светит со всех сторон сразу, поэтому лучи солнца попадают внутрь дома с каждой стороны перпендикулярно стене, как показано на рисунке (на западной стороне одно окно в строке 3, на северной стороне два окна: в столбце 2 и в отрезке столбцов [4..5]). На рисунке закрашены освещённые клетки дома.

Формат входного файла

В первой строке входного файла содержатся два целых числа R, C – размеры дома (1 ≤ R, C ≤ 10⁶) в метрах.

Во второй строке входного файла находится целое число n – количество окон на северной стороне (0 ≤ n ≤ 10⁶). В следующих n строках содержится описание окон на северной стороне: i--е окно описывается двумя числами 1 ≤ s_i, t_i ≤ C – это значит, что на северной стороне дома в столбцах от s_i до t_i включительно находится окно.

В следующей строке входного файла находится целое число m – количество окон на западной стороне (0 ≤ m ≤ 10⁶). В следующих m строках содержится описание окон на западной стороне в формате, аналогичном формату описания окон на северной стороне. Гарантируется, что никакие два окна не пересекаются.

Формат выходного файла

В единственной строке выходного файла выведите одно целое число – площадь освещаемой части дома (так как каждая клетка дома имеет площадь 1 м², то площадь освещаемой части просто равна количеству освещенных клеток).

Пример:

Решения, верно работающие при ограничениях R, C, n, m ≤ 100 будут оценены в 40 баллов.

Решения, верно работающие при ограничениях R, C ≤ 10⁶, n, m ≤ 1000 будут оценены в 60 баллов.

Решения, верно работающие при ограничениях R, C, n, m ≤ 10⁶ будут оценены в 100 баллов.

Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 12 декабря 2014 года.

Обсудить       Отправить решение



Версия для печати