| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 107 | 48 | 39 | 60.938% |
$H$개의 행과 $W$개의 열로 이루어진 격자가 있다. 각 격자 칸은 $(i, j)$로 나타내며, 이는 위에서부터 $i$번째 행, 왼쪽에서부터 $j$번째 열을 의미한다. $(i, j)$에는 임의의 정수 $A_{ij}$가 적혀 있으며, 이 값은 1ドル$ 이상 $H \times W$ 이하이다.
정수 $K$가 주어지고, $Q$개의 쿼리가 주어진다. 각 쿼리마다 좌표 $(y, x)$가 주어지는데, 이는 왼쪽 위 칸이 $(y, x)$이고 한 변의 길이가 $K$인 정사각형을 의미한다. 각 쿼리마다 주어진 정사각형에 포함된 영역의 수들을 지울 때, 나머지 격자 부분에 존재하는 서로 다른 수의 개수를 구하여라.
모든 쿼리는 독립적이다. 즉, 이전 쿼리는 다음 쿼리에 영향을 주지 않는다.
첫 번째 줄에 $H, W, K, Q$가 주어진다. (1ドル \le H, W \le 2,000円,ドル 1ドル \le K \le \min(H, W),ドル 1ドル \le Q \le 3 \times 10^5 $)
다음 $H$개의 줄에는 $W$개의 정수 $A_{ij}$가 공백으로 구분되어 주어진다. (1ドル \le A_{ij} \le H \times W $)
이후에는 $Q$개의 줄에 걸쳐 쿼리에 대한 정보가 주어진다. 각 줄에는 정수 $y$와 $x$가 주어지는데 $(y, x)$는 정사각형의 왼쪽 위 칸의 좌표를 의미한다. (1ドル \le y \le H - K + 1, 1 \le x \le W - K + 1$)
각 쿼리마다 주어진 정사각형을 제외한 나머지 격자에 존재하는 서로 다른 수의 개수를 한 줄에 하나씩 출력한다.
3 4 2 4 1 1 8 8 7 2 2 3 5 7 2 8 1 1 1 2 2 2 1 3
5 6 5 5
아래의 그림은 각 쿼리에 대해 $K \times K$ 크기의 정사각형으로 가려진 격자의 상태를 나타낸다.