32268번 - Mosaic 서브태스크다국어언어 제한함수 구현

문제

Salma plans to colour a clay mosaic on a wall. The mosaic is an $N \times N$ grid, made of $N$ initially uncoloured 1ドル \times 1$ square tiles. The rows of the mosaic are numbered from 0ドル$ to $N - 1$ from top to bottom, and the columns are numbered from 0ドル$ to $N - 1$ from left to right. The tile in row $i$ and column $j$ (0ドル ≤ i < N,ドル 0ドル ≤ j < N$) is denoted by $(i, j)$. Each tile must be coloured either white (denoted by 0ドル$) or black (denoted by 1ドル$).

To colour the mosaic, Salma first picks two arrays $X$ and $Y$ of length $N,ドル each consisting of values 0ドル$ and 1ドル,ドル such that $X[0] = Y [0]$. She colours the tiles of the topmost row (row 0ドル$) according to array $X,ドル such that the colour of tile $(0, j)$ is $X[j]$ (0ドル ≤ j < N$). She also colours the tiles of the leftmost column (column 0ドル$) according to array $Y,ドル such that the colour of tile $(i, 0)$ is $Y [i]$ (0ドル ≤ i < N$).

Then she repeats the following steps until all tiles are coloured:

• She finds any uncoloured tile $(i, j)$ such that its up neighbor (tile $(i - 1, j)$) and left neighbor (tile $(i, j - 1)$) are both already coloured.
• Then, she colours tile $(i, j)$ black if both of these neighbors are white; otherwise, she colours tile $(i, j)$ white.

It can be shown that the final colours of the tiles do not depend on the order in which Salma is colouring them.

Yasmin is very curious about the colours of the tiles in the mosaic. She asks Salma $Q$ questions, numbered from 0ドル$ to $Q - 1$. In question $k$ (0ドル ≤ k < Q$), Yasmin specifies a subrectangle of the mosaic by its:

• Topmost row $T[k]$ and bottommost row $B[k]$ (0ドル ≤ T[k] ≤ B[k] < N$),
• Leftmost column $L[k]$ and rightmost column $R[k]$ (0ドル ≤ L[k] ≤ R[k] < N$).

The answer to the question is the number of black tiles in this subrectangle. Specifically, Salma should find how many tiles $(i, j)$ exist, such that $T[k] ≤ i ≤ B[k],ドル $L[k] ≤ j ≤ R[k],ドル and the colour of tile $(i, j)$ is black.

Write a program that answers Yasmin's questions.

구현

You should implement the following procedure.

std::vector<long long> mosaic(
 std::vector<int> X, std::vector<int> Y,
 std::vector<int> T, std::vector<int> B,
 std::vector<int> L, std::vector<int> R)

• $X,ドル $Y$: arrays of length $N$ describing the colours of the tiles in the topmost row and the leftmost column, respectively.
• $T,ドル $B,ドル $L,ドル $R$: arrays of length $Q$ describing the questions asked by Yasmin.
• The procedure should return an array $C$ of length $Q,ドル such that $C[k]$ provides the answer to question $k$ (0ドル ≤ k < Q$).
• This procedure is called exactly once for each test case.

입력

출력

제한

• 1ドル ≤ N ≤ 200,円 000$
• 1ドル ≤ Q ≤ 200,円 000$
• $X[i] ∈ \{0, 1\}$ and $Y [i] ∈ \{0, 1\}$ for each $i$ such that 0ドル ≤ i < N$
• $X[0] = Y [0]$
• 0ドル ≤ T[k] ≤ B[k] < N$ and 0ドル ≤ L[k] ≤ R[k] < N$ for each $k$ such that 0ドル ≤ k < Q$

서브태스크

힌트

예제

Consider the following call.

mosaic([1, 0, 1, 0], [1, 1, 0, 1], [0, 2], [3, 3], [0, 0], [3, 2])

This example is illustrated in the pictures below. The left picture shows the colours of the tiles in the mosaic. The middle and right pictures show the subrectangles Yasmin asked about in the first and second question, respectively.

The answers to the questions (that is, the numbers of ones in the shaded rectangles) are 7ドル$ and 3ドル,ドル respectively. Hence, the procedure should return $[7, 3]$.

샘플 그레이더

Input format:

N
X[0] X[1] ... X[N-1]
Y[0] Y[1] ... Y[N-1]
Q
T[0] B[0] L[0] R[0]
T[1] B[1] L[1] R[1]
...
T[Q-1] B[Q-1] L[Q-1] R[Q-1]

Output format:

C[0]
C[1]
...
C[S-1]

Here, $S$ is the length of the array $C$ returned by mosaic.

첨부

• mosaic.zip