월간 향유회 - 색깔 사각형과 쿼리

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	512 MB	127	32	17	22.973%

문제

색깔 사각형은 내부가 비어 있고 동서남북을 이루는 선분 $4$개가 각각 $1$, $2$, $3$, $4$, $5$, $6$의 색 중 하나로 칠해져 있는 직사각형이다. 사각형의 꼭짓점은 연결된 두 선분의 색 중 더 큰 값을 가지는 색으로 칠한다.

준혁이는 색깔 사각형 $N$개를 서로 다른 두 사각형의 어떤 선분이 교차하지도, 접하지도 않도록 평면 위에 배치해 놓았다. 또, 사각형의 선분이 $x$축 또는 $y$축과 평행하도록 배치하였다.

다음 쿼리 $Q$개를 수행하자.

두 점 $(x_s, y_s), (x_e,y_e)$가 주어질 때, $(x_s, y_s)$에서 시작하여 $(x_e,y_e)$에 도착하는 임의의 경로가 사각형의 선분의 색 중 최소 몇 가지 종류의 색을 지나야 하는지 출력한다. 두 점 사이를 이동하는 경로는 평면 위의 모든 공간을 자유롭게 이동할 수 있다.

첫째 줄에 사각형의 개수 $N$이 주어진다. $(1 \leq N \leq 200\,000)$

다음 $N$개의 줄에 준혁이가 배치한 사각형의 정보를 나타내는 정수 $x_1$, $y_1$, $x_2$, $y_2$, $c_1$, $c_2$, $c_3$, $c_4$이 공백으로 구분되어 주어진다.

입력되는 사각형의 왼쪽 아래 점은 $(x_1, y_1)$, 오른쪽 위의 점은$(x_2, y_2)$이다. $(-10^9 \leq x_1<x_2 \leq 10^9;$ $-10^9 \leq y_1<y_2 \leq 10^9)$
$c_1$, $c_2$, $c_3$, $c_4$는 각각 사각형의 왼쪽 선분, 위쪽 선분, 오른쪽 선분, 아래쪽 선분의 색을 나타낸다. $(1 \leq c_i \leq 6)$

다음 줄에 쿼리의 개수 $Q$가 입력된다. $(1 \leq Q \leq 200\,000)$

다음 $Q$개의 줄에 쿼리 $x_s$, $y_s$, $x_e$, $y_e$가 입력된다. 점 $(x_s,y_s)$와 $(x_e, y_e)$은 준혁이가 배치한 사각형의 선분 위에 있지 않다. $(-10^9 \leq x_s,x_e,y_s,y_e \leq 10^9)$

$Q$개의 줄에 걸쳐 각 쿼리의 답을 한 줄에 하나씩 출력한다.

2
1 1 5 5 1 2 3 4
2 2 4 4 2 3 4 1
1
3 3 6 3

4
1 1 10 10 1 2 3 4
2 11 4 13 2 1 2 1
4 4 5 5 6 6 6 6
6 6 8 9 5 5 4 4
4
2 5 6 5
7 7 3 12
15 -1 9 9
-1 -1 5 -1

Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 11. D번