시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (언어별 추가 시간 없음) 1024 MB 38 8 7 33.333%

문제

To celebrate your team's victory at ICPC World Finals, Edsger W. Dijkstra (The inventor and namesake of Dijkstra's algorithm) will throw a fabulous party at your house in New York City. The party starts in 4 hours, so he should better start moving.

New York City is modeled as a 2-dimensional plane. Dijkstra is now in coordinate $(s_x,\ s_y)$, and your house is located in coordinate $(e_x,\ e_y)$. Dijkstra should come to your house by only moving in a direction parallel to the coordinate axes (you remember the Manhattan distance, right?). Also, there are $N$ skyscraper in an axis-parallel rectangular shape, which you can pass through its boundary, but cannot pass through anywhere strictly inside of it.

You got a phone call from Dijkstra, saying that it's too hard for him to compute the shortest path between his location and your house. Somehow, he is losing his edge. However, that's not bad news, because it's a chance for you to be cool in front of the great Dijkstra. Can you?

It is guaranteed that all $x$ coordinates are distinct and all $y$ coordinates are distinct. It is also guaranteed that no pair of rectangles overlap. It is also guaranteed that your house and Dijkstra's starting location are not inside of any rectangles.

입력

The first line contains five space-separated integers $N$, $s_x$, $s_y$, $e_x$, $e_y$.

The $i$-th line of next $N$ lines contain four space-separated integers $a_i$, $b_i$, $c_i$, $d_i$. This indicates that $i$-th skyscraper is a rectangle with its four corners located in $(a_i,\ b_i),\ (a_i,\ d_i),\ (c_i,\ b_i),\ (c_i,\ d_i)$. 

출력

Print the length of the shortest path between Dijkstra's location and your house, using the Manhattan metric.

제한

  • $1 \le N \le 250\,000$

  • $0 \le s_x,\ s_y,\ e_x,\ e_y \le 10^8$

  • $0 \le a_i < c_i \le 10^8$ ($1 \le i \le n$)

  • $0 \le b_i < d_i \le 10^8$ ($1 \le i \le n$)

  • Let $X = \{s_x,\ e_x,\ a_1,\ a_2,\ \cdots,\ a_N,\ c_1,\ c_2,\ \cdots,\ c_N\}$, all elements in $X$ are distinct.

  • Let $Y = \{s_y,\ e_y,\ b_1,\ b_2,\ \cdots,\ b_N,\ d_1,\ d_2,\ \cdots,\ d_N\}$, all elements in $Y$ are distinct.

  • No pair of rectangles share a common point.

  • Dijkstra's location and your house's location are not in any of the rectangles.

서브태스크 1 (31점)

This subtask has an additional constraint. 

  • $N \le {\color{red}{500}}$

서브태스크 2 (24점)

This subtask has an additional constraint. 

  • $N \le 5\,000$

서브태스크 3 (45점)

This subtask has no additional constraints.

예제 입력 1

3 2 14 5 1
4 6 6 10
0 7 3 9
1 2 8 5

예제 출력 1

20

예제 입력 2

1 0 500 100 503
1 0 99 1000

예제 출력 2

1097

예제 입력 3

2 2 8 10 3
3 6 6 10
7 1 8 7

예제 출력 3

15

출처

University > KAIST > 2019 KAIST RUN Spring Open Contest I번

채점

  • 예제는 채점하지 않는다.