Salma plans to colour a clay mosaic on a wall.
The mosaic is an grid,
made of
initially uncoloured
square tiles.
The rows of the mosaic are numbered from
to
from top to bottom,
and the columns are numbered from
to
from left to right.
The tile in row
and column
(
,
) is denoted by
.
Each tile must be coloured either
white (denoted by
) or black (denoted by
).
To colour the mosaic, Salma first picks two arrays and
of length
,
each consisting of values
and
, such that
.
She colours the tiles of the topmost row (row
) according to array
,
such that the colour of tile
is
(
).
She also colours the tiles of the leftmost column (column
) according to array
,
such that the colour of tile
is
(
).
Then she repeats the following steps until all tiles are coloured:
- She finds any uncoloured tile
such that its up neighbor (tile
) and left neighbor (tile
) are both already coloured.
- Then, she colours tile
black if both of these neighbors are white; otherwise, she colours tile
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 questions, numbered from
to
.
In question
(
),
Yasmin specifies a subrectangle of the mosaic by its:
- Topmost row
and bottommost row
(
),
- Leftmost column
and rightmost column
(
).
The answer to the question is the number of black tiles in this subrectangle.
Specifically, Salma should find how many tiles exist,
such that
,
,
and the colour of tile
is black.
Write a program that answers Yasmin's questions.
Implementation Details
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)
,
: arrays of length
describing the colours of the tiles in the topmost row and the leftmost column, respectively.
,
,
,
: arrays of length
describing the questions asked by Yasmin.
- The procedure should return an array
of length
, such that
provides the answer to question
(
).
- This procedure is called exactly once for each test case.
Constraints
and
for each
such that
and
for each
such that
Subtasks
Subtask | Score | Additional Constraints |
---|---|---|
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | No additional constraints. |
Example
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 .
Sample Grader
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, is the length of the array
returned by
mosaic
.
Attachment Package
The sample grader along with sample test cases are available here.
Comments