USACO 2020 January Contest, Gold
Problem 3. Springboards
Contest has ended.
Log in to allow submissions in analysis mode
Bessie is in a 2D grid where walking is permitted only in directions parallel to
one of the coordinate axes. She starts at the point $(0,0)$ and wishes to reach
$(N,N)$ ($1\le N\le 10^9$). To help her out, there are $P$ ($1\le P\le 10^5$)
springboards on the grid. Each springboard is at a fixed point $(x_1,y_1)$ and
if Bessie uses it, she will land at a point
$(x_2,y_2)$.
Contest has ended. No further submissions allowed.
Bessie is a progress-oriented cow, so she only permits herself to walk up or right, never left nor down. Likewise, each springboard is configured to never go left nor down. What is the minimum distance Bessie needs to walk?
SCORING:
- Test cases 2-5 satisfy $P \le 1000$.
- Test cases 6-15 satisfy no additional constraints.
INPUT FORMAT (file boards.in):
The fist line contains two space-separated integers $N$ and $P$.The next $P$ lines each contains four integers, $x_1$, $y_1$, $x_2$, $y_2$, where $x_1 \le x_2$ and $y_1 \le y_2.$
All springboard and target locations are distinct.
OUTPUT FORMAT (file boards.out):
Output a single integer, the minimum distance Bessie needs to walk to reach $(N,N)$.SAMPLE INPUT:
3 2 0 1 0 2 1 2 2 3
SAMPLE OUTPUT:
3
Bessie's best path is:
- Bessie walks from (0,0) to (0,1) (1 unit).
- Bessie springs to (0,2).
- Bessie walks from (0,2) to (1,2) (1 unit).
- Bessie springs to (2,3).
- Bessie walks from (2,3) to (3,3) (1 unit).
Problem credits: Pedro Paredes