LCC '21 Contest 6 S3 - Empire

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem type

On an field of size N rows by M columns, Matthew is running a construction operation.

He selects T rectangular plots of land as sites to build barriers. Each plot of land is bounded by the rectangle with corners (x_{1_{i}}, y_{1_{i}}) and (x_{2_{i}}, y_{2_{i}}).

After selecting the sites, he wants to know whether its possible to traverse from (1, 1) to (M, N) while avoiding barriers. Movement is done only in cardinal directions (up, down, left, right).

Input Specifications

The first line will contain two space-separated integers, N and M (1 \le N, M \le 10^6), representing the number of rows and columns on the field.

The second line will contain T (1 \le T \le 10^3), representing the number of marked plots of land.

The next Q lines each contain four space-separated integers, y_{1_{i}}, x_{1_{i}}, y_{2_{i}}, and x_{2_{i}}, representing the plots of land. These coordinates are guaranteed to be within the boundaries of the field.

Output Specifications

Output YES if the traversal is possible or NO otherwise.

Sample Input 1

5 6
2
3 1 4 3
1 3 3 6

Sample Output 1

NO

Sample Explanation 1

The following image represents the grid, where black cells are marked cells.

Sample Input 2

5 6
2
3 1 4 3
3 5 4 6

Sample Output 2

YES

Sample Explanation 2

The following image represents the grid, where black cells are marked cells.


Comments

There are no comments at the moment.