레이팅 미적용설명
베시는 좌표축 중 하나와 평행한 방향으로만 걸을 수 있는 2차원 격자 위에 있다. 베시는 점 \((0,0)\)에서 출발하여 \((N,N)\)(\(1\le N\le 10^9\))에 도달하고 싶다. 베시를 돕기 위해 격자 위에는 \(P\)개(\(1\le P\le 10^5\))의 스프링보드가 있다. 각 스프링보드는 고정된 점 \((x_1,y_1)\)에 있으며, 베시가 이를 사용하면 점 \((x_2,y_2)\)에 착지하게 된다.
베시는 전진 지향적인 소이므로, 위쪽 또는 오른쪽으로만 걷고 왼쪽이나 아래쪽으로는 절대 걷지 않는다. 마찬가지로 각 스프링보드도 왼쪽이나 아래쪽으로는 절대 가지 않도록 설정되어 있다. 베시가 걸어야 하는 최소 거리는 얼마인가?
문제 제공: Pedro Paredes
제약
점수 배점
- 테스트 케이스 2-5는 \(P \le 1000\)을 만족한다.
- 테스트 케이스 6-15는 추가 제약이 없다.
문제 제공: Pedro Paredes
입력 형식
첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(P\)가 주어진다.
다음 \(P\)개의 줄에는 각각 네 정수 \(x_1\), \(y_1\), \(x_2\), \(y_2\)가 주어지며, \(x_1 \le x_2\)이고 \(y_1 \le y_2\)이다.
모든 스프링보드의 위치와 착지 위치는 서로 다르다.
출력 형식
베시가 \((N,N)\)에 도달하기 위해 걸어야 하는 최소 거리를 나타내는 정수 하나를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
boards.in · 출력을 쓸 파일 boards.out예제 1
입력
3 2
0 1 0 2
1 2 2 3출력
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).
The total walking length of Bessie's path is 3 units.
문제 정보
태그