Rainy Days

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 3.5s
Memory limit: 256M

Author:
Problem type

In Rainyville, it rains quite a lot. Despite residents getting used to the frequent rain, they still would rather avoid it when walking outside. The side view of a sidewalk (the view as if you were facing the sidewalk from across the street) can be represented by an M by N grid with M rows and N columns, where the bottom left corner has coordinates (0,0). The rain will come from just above this side view, at row M (not visible in this rectangular side view). When walking across this sidewalk, there are certain things that block the rain, such as trees and balconies. The K blocks will ensure that each cell within the same vertical column below the block will not be rained on. Consider the following example:

drawing

In the diagram, the blue cells represent rain, black represent blocks, and white represent cells safe from the rain. In this example, there is a 6 by 5 grid with blocks at (0,2), (1,4), (2,0), (2,3), (3,1), and (5,2). Rain falls from the very top, and it will fall until it hits a block, at which point any cells below that block will be safe from the rain. In this case, there are 11 cells safe from the rain. Notice that blocked cells do not count.

Given the blocks in a side view grid of a sidewalk, determine the number of cells that are safe from the rain.

Constraints

1\le N,M \le 10^8

1\le K\le \min(N\times M, 10^6)

It is guaranteed that each blocked cell will be unique.

Subtask 1 [20%]

1\le N,M \le 100

Subtask 2 [80%]

No additional constraints

Input Specification

The first line will contain integers N, M, and K, each separated by a space.

The next K lines will contain two spaced integers each, representing the coordinates of the blocked cells (as described in the problem statement).

It is guaranteed that each cell will be unique.

Output Specification

On a single line, output the number of cells that are safe from the rain.

Sample Input 1

6 5 6
0 2
1 4
2 0
2 3
3 1
5 2

Sample Output 1

11

Explanation for Sample Output 1

This is the sample case described in the problem statement.

Sample Input 2

8 8 8
7 6
2 4
5 3
1 1
6 1
3 2
6 4
0 5

Sample Output 2

24

Comments

There are no comments at the moment.