24939번 - Boardle 서브태스크

Boardle 게임은 $N \times M$ 크기의 격자판에서 이루어집니다. 격자판의 마주보는 두 꼭짓점은 $(1, 1)$과 $(N, M)$입니다. 격자판의 $NM$개 칸 중 하나에 보물이 숨겨져 있습니다. 보물을 찾으면 게임에서 승리합니다.

보물을 찾기 위해, 당신은 아래와 같이 $Q$회의 질문을 했습니다.

• 점 $(x, y)$를 기준으로, 보물이 어느 방향에 숨겨져 있습니까?

그 결과는 동/서/남/북/북동/북서/남동/남서/일치 중 하나로 나타낼 수 있습니다. 이때 동쪽은 $+x$, 서쪽은 $-x$, 북쪽은 $+y$, 남쪽은 $-y$에 해당하는 방향입니다. $Q$개의 질문에 대한 대답을 통해, 보물이 있을 수 있는 격자 칸의 후보의 수를 구해 봅시다.

첫 줄에는 격자판의 크기를 나타내는 정수 $N$과 $M$이 주어집니다.

둘째 줄에는 질의의 수 $Q$가 띄어쓰기를 사이에 두고 주어집니다.

셋째 줄부터 $Q+2$번 줄까지, $i+2$번 줄에는 $i$번 질문에 대한 정보가 $x_i$ $y_i$ $d_i$의 형태로 주어집니다. $x_i$와 $y_i$는 $i$번째로 질문한 점의 위치를 나타냅니다. $d_i$는 1 이상 9 이하의 정수로, 아래와 같이 각 방향에 대응됩니다.

$1 \le d_i \le 4$인 경우 정확히 해당 방향에 있다는 의미입니다. 즉, $d_i =4$인 경우 보물은 선택한 점의 북서쪽이나 북동쪽이 아닌 정북 방향에 위치합니다.

보물이 숨겨져 있을 수 있는 칸의 개수를 출력합니다. 이러한 후보 칸이 반드시 존재함이 보장됩니다.

• $1 \le N, M \le 10^9$
• $1 \le Q \le 10^5$
• $1 \le x_i \le N$ ($1 \le i \le Q$)
• $1 \le y_i \le M$ ($1 \le i \le Q$)
• $1 \le d_i \le 9$ ($1 \le i \le Q$)