P2692 Coverage

In WSR's school, $B$ boys and $G$ girls have come to a huge playground to sweep the ground.

The playground can be viewed as an $N$-by-$M$ grid of cells. As shown in Figure (1), this is a $4$-by-$5$ grid. Each boy is responsible for sweeping some consecutive rows, and each girl is responsible for sweeping some consecutive columns. For example, suppose there are two boys: the first boy is responsible for rows $1, 2$, and the second boy is responsible for row $4$, shown in blue in Figure (2). The swept regions may overlap. For instance, suppose there are also two girls: the first girl is responsible for columns $3, 4$, and the second girl is responsible for columns $4, 5$, shown in red in Figure (3). From Figure (3), it is easy to see that the number of colored cells is 18, i.e., these four students have swept a total of 18 cells.  The teacher asks WSR to quickly compute, given the cleaning plan data, how many cells have been swept in total.

The first line contains $4$ positive integers: $N, M, B, G$. Here, $N$ is the number of rows, $M$ is the number of columns, $B$ is the number of boys, and $G$ is the number of girls. The next $B$ lines each contain two integers $x, y$. Each line indicates that a boy is responsible for rows $x$ through $y$ inclusive (a total of $y - x + 1$ rows), with the guarantee that $1 \le x \le y \le N$. Then the next $G$ lines each contain two integers $x, y$. Each line indicates that a girl is responsible for columns $x$ through $y$ inclusive (a total of $y - x + 1$ columns), with the guarantee that $1 \le x \le y \le M$.

Output a single integer, the swept area (i.e., the total number of cells).

If you are not sure, try drawing a diagram yourself. Constraints: - For $80\%$ of the testdata, $1 \le N,M,B,G \le 10^2$. - For $100\%$ of the testdata, $ 1 \le N,M,B,G \le 5 \times 10^3$. Translated by ChatGPT 5