| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 12 | 10 | 10 | 83.333% |
Bob은 2차원 격자무늬 평면에 색종이와 블록을 올려놓고 재미있는 놀이를 하고 있다. 각 블록의 크기는 1x1로 모두 동일하며, 같은 위치에 블록을 여럿 쌓을 수도 있다. 조금 더 구체적으로, $N$개의 블록이 있을 때 $i$ 번째 블록의 위치는 $(x_i, y_i)$ 라 하자. 이 문제의 예제에서 좌측 상단이 (1, 1) 이며 좌-우가 $x$축이다. 가령 아래 그림에서 좌측 상단의 경우 1번 블록은 (2, 2) 위치에 있고 3번 블록은 (4, 3) 위치에 있다.
Bob은 또한 $M$ 장의 색종이를 갖고 있는데 $j$ 번째 색종이의 크기는 가로 $w_j$ 칸 세로 $h_j$ 칸 이며, 이 문제에서는 색종이를 회전하지 않는다고 하자.
Bob이 블록과 색종이를 이용해 다양한 놀이를 하던 중, 이를 지켜보던 Alice는 동생 Bob에게 아래와 같은 문제를 풀어보라고 했다.
이제, 위 정의를 이용하여 Alice는 Bob에게 총 $Q$ 개의 질문을 하는데, $k$ 번째 질문은 두 개의 정수 $L_k, U_k$ 로 표현된다:
예를 들어 위 그림의 경우, $N = 5$ 이고 블록의 좌표는 $x = [2, 4, 8, 7, 3]$ 과 $y = [2, 3, 3, 4, 5]$ 로 표현할 수 있다. $M = 3$장의 색종이는 앞서 언급한 순서대로 크기가 $w = [4, 8, 9]$ 그리고 $h = [4, 4, 3]$ 이라 하자.
만약 Alice가 총 $Q = 5$개의 질문을 하고, $L = [0, 1, 0, 1, 2]$ 그리고 $U = [2, 3, 3, 1, 3]$ 이라면 각 질문에 대한 답은 아래와 같다.
입력으로 $N$개의 블록의 위치, $M$장의 색종이 크기, 그리고 Alice의 질문 $Q$개가 주어졌을 때, 각 질문에 대한 답을 구하여 Bob을 도와주자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N, M, Q$ 가 공백으로 구분되어 주어진다. 다음 $N$줄은 각 블록의 위치를 나타내며 각 줄에 $x_i$ 와 $y_i$가 공백으로 구분되어 주어진다. 다음 $M$줄은 각 색종이의 크기를 나타내며 각 줄에 $w_j$ 와 $h_j$가 공백으로 구분되어 주어진다. 다음 $Q$줄은 Alice의 질문을 나타내며 각 줄에 $L_k$ 와 $U_k$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 한 줄에 출력한다 -- 이 줄에는 $Q$개의 질문에 대한 답을 공백으로 구분하여 출력한다.
2 5 3 5 2 2 8 3 4 3 7 4 3 5 4 4 8 4 9 3 0 2 1 3 0 3 1 1 2 3 5 3 3 1 1 2 2 1 1 2 2 3 3 1 3 3 1 2 3 0 1 1 2 0 3
3 4 5 1 3 3 2 5
예제 1: 본문에서 다루었다.
예제 2: 같은 위치에 여러 블록이 있을 수 있다.