Paper cutting - MarisaOJ: Marisa Online Judge

Paper cutting

Time limit: 1000 ms
Memory limit: 256 MB
Given a sheet of paper with dimensions $H \times W$. Cut $n$ parallel cuts along the edges of the paper, and determine how many parts the paper is divided into. ### Input - The first line contains three integers $W$, $H$, and $n$. - The next $n$ lines each contain four integers $x_1$, $y_1$, $x_2$, $y_2$, indicating a cut from position $(x_1, y_1)$ to $(x_2, y_2)$. ### Output - Print an integer representing the number of parts the paper is divided into. ### Constraints - $1 \leq n \leq 10^5$. - $1 \leq W, H \leq 10^9$. - $1 \leq x_1 \leq x_2 \leq W$. - $1 \leq y_1 \leq y_2 \leq H$. ### Example Input: ``` 10 10 5 6 0 6 7 0 6 7 6 2 3 9 3 2 3 2 10 1 9 8 9 ``` Output: ``` 4 ```
Topic
Data structure
DSU
Rating 2300
Source JOI
Solution (0) Solution